Given two integers A and B.

Let P denote a sequence of N [prime numbers] such that the sum of the sequence is A.
Let Q denote a sequence of M prime numbers such that the sum of the sequence is B.

Let X denote the maximum absolute difference between P_{i} and Q_{j} among all valid pairs (i,j) such that (1 ≤ i ≤ N) and (1 ≤ j ≤ M).
Find the minimum possible value of X over all possible sequences P and Q.

More formally, for all possible sequences P and Q, find the minimum value of \texttt{max}(|P_{i} - Q_{j}|), where (1 ≤ i ≤ N) and (1 ≤ j ≤ M).

Print -1 if any one of the sequences cannot be formed.

Note that, |X| denotes the absolute value of a number X. For example, |-4| = 4 and |7| = 7.

------ Input Format ------ 

- First line will contain T, the number of test cases. Then the test cases follow.
- Each test case contains two integers A and B.

------ Output Format ------ 

For each test case, find the minimum possible value of the maximum absolute difference between P_{i} and Q_{j} for (1 ≤ i ≤ N) and (1 ≤ j ≤ M). If any of the sequences can not be formed, print -1 instead.

------ Constraints ------ 

$1 ≤T ≤10^{5}$
$1 ≤A ≤10^{18}$
$1 ≤B ≤10^{18}$

----- Sample Input 1 ------ 
2
3 6
3 2
----- Sample Output 1 ------ 
0
1
----- explanation 1 ------ 
Test case $1$: Let $P=\{3\}$ and $Q=\{3,3\}$.  
The maximum absolute difference is $0$. It can be shown that the maximum absolute difference can not be less than $0$.

Test case $2$: The only possible sequences are $P=\{3\}$ and $Q=\{2\}$.  
The maximum absolute difference is $1$. It can be shown that the maximum absolute difference can not be less than $1$.

Difficulty: MEDIUM
Tags: Number theory

Mathematics

Starter code:

Solutions:
import math
t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	if a <= 1 or b <= 1:
		print(-1)
	elif math.gcd(a, b) > 1:
		print(0)
	else:
		print(1)


import math

def check(a, b):
	if a == 1 or b == 1:
		print('-1')
	elif math.gcd(a, b) > 1:
		print(0)
	else:
		print(1)
t = int(input())
while t > 0:
	(x, y) = map(int, input().split())
	check(x, y)
	t = t - 1


import math
n = int(input())
for i in range(n):
	(a, b) = map(int, input().split(' '))
	if a <= 1 or b <= 1:
		print(-1)
	elif math.gcd(a, b) > 1:
		print(0)
	else:
		print(1)


from math import gcd
for i in range(int(input())):
	(a, b) = map(int, input().split())
	if a != 1 and b != 1:
		if gcd(a, b) == 1:
			print(1)
		else:
			print(0)
	else:
		print(-1)


import math
T = int(input())
for i in range(T):
	(A, B) = map(int, input().split())
	if A == 1 or B == 1:
		print(-1)
	elif math.gcd(A, B) == 1:
		print(1)
	else:
		print(0)


from math import gcd
for _ in range(int(input())):
	(A, B) = map(int, input().split())
	if A == 1 or B == 1:
		print(-1)
	elif gcd(A, B) == 1:
		print(1)
	else:
		print(0)


from math import gcd
t = int(input())
for j in range(t):
	(a, b) = map(int, input().split())
	if a < 2 or b < 2:
		print(-1)
	elif gcd(a, b) == 1:
		print(1)
	else:
		print(0)


from math import gcd
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	if m == 1 or n == 1:
		print(-1)
	elif gcd(m, n) == 1:
		print(1)
	else:
		print(0)


from math import gcd
for _ in range(int(input())):
	(X, Y) = map(int, input().split(' '))
	if X == 1 or Y == 1:
		print(-1)
	else:
		G_XY = gcd(X, Y)
		if G_XY != 1:
			print(0)
		else:
			print(1)


import math

def solution():
	(A, B) = map(int, input().split())
	if A < 2 or B < 2:
		print(-1)
	elif math.gcd(A, B) == 1:
		print(1)
	else:
		print(0)
T = int(input())
for _ in range(T):
	solution()


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
T = int(input())
for _ in range(T):
	(a, b) = map(int, input().split())
	if a == 1 or b == 1:
		print(-1)
	elif gcd(a, b) > 1:
		print(0)
	else:
		print(1)


ll = lambda : map(int, input().split())
t = lambda : int(input())
ss = lambda : input()
lx = lambda x: map(int, input().split(x))
yy = lambda : print('YES')
nn = lambda : print('NO')
from math import log10, log2, ceil, factorial as fac, gcd, inf, sqrt, log, floor
from bisect import bisect_right as br, bisect_left as bl, insort
from collections import Counter
mod = 10 ** 9 + 7

def Nprime(n):
	if n == 2 or n == 3:
		return 0
	if n == 1:
		return 1
	i = 2
	while i * i <= n:
		if n % i == 0:
			return 1
		i += 1
	return 0

def sum_(a, n):
	d = 4
	s = n * (2 * a + (n - 1) * d) // 2
	return s

def find(low, high, p, ans):
	while low <= high:
		mid = (low + high) // 2
		temp = pow(mid, p)
		if temp == ans:
			return mid
		elif temp > ans:
			high = mid - 1
		else:
			low = mid + 1
	return high

def max_(arr, n, k):
	for i in range(k, n):
		s -= arr[i - k]
		s += arr[i]
		ans = max(s, ans)
	return ans

def f(x, y, m):
	if y <= m and gcd(x, y) > 1:
		return 1
	return 0
for _ in range(t()):
	(a, b) = ll()
	if a == 1 or b == 1:
		print(-1)
		continue
	if gcd(a, b) > 1:
		print(0)
	else:
		print(1)


import math
T = int(input())
for i in range(T):
	(x, y) = input().split()
	(X, Y) = (max(int(x), int(y)), min(int(x), int(y)))
	L = X / Y
	if int(x) < 2 or int(y) < 2:
		print(-1)
	elif math.gcd(X, Y) != 1:
		print(0)
	else:
		print(1)


import math
T = int(input())
for _ in range(T):
	(A, B) = [int(x) for x in input().split()]
	div = math.gcd(A, B)
	if A < 2 or B < 2:
		print('-1')
	elif div == 1:
		print(1)
	else:
		print(0)


def gcd(x, y):
	return gcd(y, x % y) if x % y else y
for _ in range(int(input())):
	(A, B) = [int(x) for x in input().split()]
	if 1 in [A, B]:
		print(-1)
	elif gcd(A, B) > 1:
		print(0)
	else:
		print(1)


from math import gcd
t = int(input())
for i in range(t):
	l = input().split()
	a = int(l[0])
	b = int(l[-1])
	if a == 1 or b == 1:
		print(-1)
	elif gcd(a, b) == 1:
		print(1)
	else:
		print(0)


from math import gcd
for _ in range(int(input())):
	(i, j) = map(int, input().split(' '))
	if i == 1 or j == 1:
		print(-1)
	else:
		GCD_i_j = gcd(i, j)
		if GCD_i_j != 1:
			print(0)
		else:
			print(1)


import math
t = int(input())
for _ in range(t):
	(p, q) = map(int, input().split())
	r = math.gcd(p, q)
	if p <= 1 or q <= 1:
		print('-1')
	elif r == 1:
		print(1)
	else:
		print(0)


import math as m
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	if a < 2 or b < 2:
		print('-1')
	elif m.gcd(a, b) == 1:
		print('1')
	else:
		print('0')


import math

def solve():
	(a, b) = map(int, input().split())
	if a < 2 or b < 2:
		print(-1)
	elif math.gcd(a, b) == 1:
		print(1)
	else:
		print(0)
t = int(input())
while t > 0:
	t = t - 1
	solve()


import math
t = int(input())
while t:
	(a, b) = map(int, input().split())
	r = math.gcd(a, b)
	if a == 1 or b == 1:
		print(-1)
	elif r == 1:
		print(1)
	else:
		print(0)
	t -= 1


from math import gcd
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	g = gcd(a, b)
	if a == 1 or b == 1:
		print(-1)
		continue
	if g != 1:
		print(0)
	else:
		print(1)


from math import gcd
q = int(input())
for i in range(q):
	(x, y) = map(int, input().split())
	g = gcd(x, y)
	if x == 1 or y == 1:
		print(-1)
		continue
	if g != 1:
		print(0)
	else:
		print(1)


import io, os, sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	return input().strip()

def invr():
	return map(int, input().split())

def outp(n):
	sys.stdout.write(str(n) + '\n')

def outlt(lst):
	sys.stdout.write(' '.join(map(str, lst)) + '\n')

def outplt(lst):
	sys.stdout.write('\n'.join(map(str, lst)))
from math import gcd
ans = []
for _ in range(inp()):
	(A, B) = inlt()
	ans.append(-1 if 1 in [A, B] else 1 if gcd(A, B) == 1 else 0)
outplt(ans)


from math import gcd
ans = []
for _ in range(int(input())):
	(A, B) = [int(x) for x in input().split()]
	ans.append(-1 if 1 in [A, B] else 1 if gcd(A, B) == 1 else 0)
print(*ans, sep='\n')


import math

def solution():
	(A, B) = map(int, input().split())
	if A < 2 or B < 2:
		print(-1)
	elif math.gcd(A, B) == 1:
		print(1)
	else:
		print(0)
T = int(input())
while T > 0:
	solution()
	T -= 1


import math
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	print(-1 if min(a, b) < 2 else 0 if math.gcd(a, b) > 1 else 1)


import math
t = int(input())
for _ in range(t):
	(x, y) = map(int, input().split())
	if x < 2 or y < 2:
		print(-1)
	elif math.gcd(x, y) == 1:
		print(1)
	else:
		print(0)


def gcd(x, y):
	if y == 0:
		return x
	else:
		return gcd(y, x % y)
t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	if a == 1 or b == 1:
		print(-1)
	else:
		c = gcd(a, b)
		if c == 1:
			print(1)
		else:
			print(0)


import math
T = int(input())
while T:
	arr = list(map(int, input().split()))
	A = arr[0]
	B = arr[1]
	if A == 1 or B == 1:
		print(-1)
	elif math.gcd(A, B) > 1 or A == B:
		print(0)
	else:
		print(1)
	T -= 1


import math

def solve():
	(a, b) = map(int, input().split())
	if a < 2 or b < 2:
		print(-1)
	elif math.gcd(a, b) == 1:
		print(1)
	else:
		print(0)
t = int(input())
for i in range(t):
	solve()


from math import gcd

def highest(num1, num2):
	temp_var = gcd(num1, num2)
	return temp_var

def check(num1, num2):
	ini = num1
	fin = num2
	if ini == 1 or fin == 1:
		print('-1')
	elif highest(ini, fin) == 1:
		print('1')
	elif ini <= fin or fin <= ini:
		print('0')
test_cses = int(input())
for ele in range(test_cses):
	(ini, fin) = map(int, input().split())
	check(ini, fin)


import math

def solve(A, B):
	if A == 1 or B == 1:
		return -1
	elif math.gcd(A, B) == 1:
		return 1
	else:
		return 0

def main():
	T = int(input())
	for _ in range(T):
		(A, B) = map(int, input().split())
		ans = solve(A, B)
		print(ans)
main()


import math
t = int(input())
for _ in range(t):
	(a, b) = [int(i) for i in input().split()]
	g = math.gcd(a, b)
	if a == 1 or b == 1:
		print('-1')
	elif a % 2 == 0 and b % 2 == 0 or g > 1:
		print('0')
	else:
		print('1')


import os, sys, math, cmath, time, collections
from collections import deque, Counter, OrderedDict, defaultdict
from heapq import nsmallest, nlargest, heapify, heappop, heappush, heapreplace
from math import ceil, floor, log, log2, sqrt, gcd, factorial, pow, pi
from bisect import bisect_left, bisect_right
from functools import reduce

def input_as_array():
	return list(map(int, input().split()))
start_time = time.time()

def main():
	(a, b) = input_as_array()
	if min(a, b) <= 1:
		print(-1)
		return
	if gcd(a, b) > 1:
		print(0)
		return
	else:
		print(1)
		return
if os.path.exists('data.in'):
	sys.stdin = open('data.in', 'r')
	sys.stdout = open('data.out', 'w')
testcases = int(input())
for i in range(testcases):
	main()
if os.path.exists('data.in'):
	print(f'Time Elapsed: {time.time() - start_time} seconds')
	sys.stdout.close()