#include <iostream>
using namespace std;
unsigned long long int gcd(unsigned long long int a, unsigned long long int b)
{
	if (a == 0)
		return b;
	return gcd(b % a, a);
}
int main()
{
	int t;
	cin >> t;
	while (t > 0)
	{
		unsigned long long int a, n;
		cin >> n >> a;
		unsigned long long int b = n;
		while (gcd(a, b) != 1)
			b--;
		cout << b << endl;
		t--;
	}
}