#include<stdio.h>

int f1(int a,int b) {
	if(a % b == 0) return b;
	else
		return f1(b,a%b);
}

int main() {
	int t,i;
	scanf("%d",&t);
	while(t--) {
		int a,b;
		scanf("%d%d",&a,&b);
		for(i=b+1; i<=a*b; i++) {
			if(b == f1(a,i)) {
				printf("%d\n",i);
				break;
			}
		}
	}
	return 0;
}