t = int(input())

for i in range(t):
	n,m = map(int, input().split())
	if n <= m:
		mi = n
	else:
		mi = m
	
	lcd = -1
	

	if n == 1 or m == 1:
		lcd = -1
	elif m == n:
		lcd = m
	elif n<=1 or m<=1:
		lcd = -1
		
	elif n % 2 != 0 or m % 2 != 0:
		k = 3
		if mi == k:
			lcd= k
		else:	
			while mi/2 <= k:
				if m % k == 0 and n % k == 0:
					lcd = k
					break

				k = k+2
			
		
	else:
		k = 2
		
	
		for _ in range(mi):
			if m % k == 0 and n % k == 0:
				lcd = k
				break
			
			k = k+1
			
			

	print(lcd)