#include <iostream>
using namespace std;
int gcd(int a,int b){
	if(b==0)return a;
	else return gcd(b,a%b);
}
long long lcm(int a,int b){
	return a*b/gcd(a,b);
}
bool is_prime(int x){
	if(x==2||x==3)return 1;
	for(int i=2;i*i<=x;i++){
		if(x%i==0)return 0;
	}
	return 1;
}
int prime[26]={2,3,5,7,11,13,15,17,19,23,29,37,31,43,47,41,53,59,61,67,71,73,79,83,89,97};
int findp(int x){
	for(int i=0;i<=25;i++){
		if(x%prime[i]==0)return prime[i];
	}
	return 0;
}
int T;
signed main(){
	cin >> T;
	while(T--){
		int a,b;
		cin >> a >> b;
		if(a>b)swap(a,b);
		if(b%a==0){
			if(a==b)puts("0");
			else cout << b << endl;
		}
		else if(gcd(a,b)>1)
			cout << lcm(gcd(a,b),a)+lcm(gcd(a,b),b) << endl;
		else if(gcd(a,b)==1){
			if(is_prime(a)&&is_prime(b)){
				cout << lcm(a,b) << endl;
			}else{
				if(is_prime(a))cout << lcm(a,findp(b))+b << endl;
				else if(is_prime(b))cout << lcm(b,findp(a))+a << endl;
				else{
					if(findp(a)<findp(b))cout << lcm(b,findp(a))+a << endl;
					else cout << lcm(a,findp(b))+b << endl;
				}
			}
		}
	}
}