#include<stdio.h>
int f(int m, int n) {
     while (n != 0) {
         int r = m % n;
         m = n;
         n = r;
     }
     return m;
}

int main(void){
	int i,j,m,n,p;
	scanf("%d",&i);
	while(i--){
		scanf("%d%d",&m,&n);
		j=m/n;
		for(p=2;p!=1;p++){
			if(f(j,p)==1){
			    printf("%d\n",p*n); 
			    p=1;
		    }
			if(p==1){
				break;
			}					
		} 
		p=2;	    			
	}
}