#include<stdio.h> 
int gcd(int a,int b) {
    return b==0?a:gcd(b,a%b);
 }
 
int main(){
	int a,b,c,n;
	scanf("%d",&n);
	
	while(n--){
		scanf("%d %d",&a,&b);
		for(c=b+1;;c++){
			if(gcd(a,c)==b){
				printf("%d\n",c);
				break;
			}
		}
	}
	
}