#include <iostream>

using namespace std;

int main()
{
    int t;
	cin >> t;
	int n, m;
	while (t-- && cin >> n >> m)
	{
		int mn = min(n, m);
		int ans = -1;
		for (int i = 2; i * i <= mn; i++)
		{
			if (n % i == 0 && m % i == 0)
			{
				ans = i;
				break;
			}
		}
		if (ans == -1 && mn > 1 && max(n, m) % mn == 0)
		{
			ans = mn;
		}
		cout << ans << "\n";
	}
}