Farmer Feb has three fields with potatoes planted in them. He harvested x potatoes from the first field, y potatoes from the second field and is yet to harvest potatoes from the third field. Feb is very superstitious and believes that if the sum of potatoes he harvests from the three fields is a prime number (http://en.wikipedia.org/wiki/Prime_number), he'll make a huge profit. Please help him by calculating for him the minimum number of potatoes that if harvested from the third field will make the sum of potatoes prime. At least one potato should be harvested from the third field.

-----Input-----
The first line of the input contains an integer T denoting the number of test cases. Each of the next T lines contain 2 integers separated by single space: x and y.

-----Output-----
For each test case, output a single line containing the answer.

-----Constraints-----
- 1 ≤ T ≤ 1000
- 1 ≤ x ≤ 1000
- 1 ≤ y ≤ 1000

-----Example-----
Input:
2
1 3
4 3

Output:
1
4

-----Explanation-----

In example case 1: the farmer harvested a potato from the first field and 3 potatoes from the second field. The sum is 4. If he is able to harvest a potato from the third field, that will make the sum 5, which is prime. Hence the answer is 1(he needs one more potato to make the sum of harvested potatoes prime.)

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
import math
try:
 def prime(n):
  for i in range(2, int(math.sqrt(n)) + 1):
   if n % i == 0:
    return False
  return True
    
 for t in range(int(input())):
  x, y = list(map(int, input().split()))
  s = x + y 
  i = s
  while(1):
   if prime(s + 1):
    ans = s + 1
    break
   else:
    s += 1
  print(ans - i)

except: pass


# cook your dish here
t = int(input())
def isPrime(num):
 c = 0
 for i in range(2,num):
  if num % i == 0:
   c = c + 1 
 if c == 0:
  return 0
 else:
  return 1
for i in range(t):
 a,b = list(map(int,input().split()))
 i = 1
 res = 0
 while(isPrime(a+b+i)):
  res = res + 1
  i = i + 1
 print(res + 1)
  


# cook your dish here
def prime(n):
 for i in range(2,(n//2)+1):
  if(n%i ==0):
   return("no")
   break
 else:
  return("yes")
for i in range(int(input())):
 a,b=map(int,input().split())
 x=a+b+1
 while(1):
  if(prime(x)=="yes"):
   ans=x
   break
  else:
   x+=1
 print(x-(a+b))

# cook your dish here
def prime(n):
 for i in range(2,(n//2)+1):
  if(n%i ==0):
   return("no")
   break
 else:
  return("yes")
for i in range(int(input())):
 a,b=map(int,input().split())
 x=a+b+1
 while(1):
  if(prime(x)=="yes"):
   ans=x
   break
  else:
   x+=1
 print(x-(a+b))

import math as m
def isprime(n):
 for i in range(2,int(m.sqrt(n))+1):
  if(n%i==0):
   return False
 return True

for _ in range(int(input())):
 x,y=map(int,input().split())
 z=(x+y)
 i=z
 while(True):
  if isprime(z+1):
   ans=z+1
   break
  else:
   z+=1
 print(ans-i)

import math as m
def isprime(n):
 for i in range(2,int(m.sqrt(n))+1):
  if(n%i==0):
   return False
 return True

for _ in range(int(input())):
 x,y=map(int,input().split())
 z=(x+y)
 i=z
 while(True):
  if isprime(z+1):
   ans=z+1
   break
  else:
   z+=1
 print(ans-i)

n=int(input())
for i in range(0,n):
 a,b=list(map(int, input().split()))
 c=a+b
 n=1
 while(True):
  s=c+n
  for j in range(2,s):
   if s%j==0:
    break
  else:
   break
  n+=1
 print(n)


t=int(input())
def prime(n):
 for i in range(2,int(n/2)+1):
  if(n%i==0):
   return 0
 else:
  return 1
for k in range(t):
 line=input().split()
 x=int(line[0])
 y=int(line[1])
 s=x+y+1
 c=1
 while (1):
  if (prime(s)==0):
   c=c+1
   s=s+1
  else:
   print(c)
   break

import math


def isPrime(n):
 flag = 0
 for j in range(2, int(n)):
  if n % j == 0:
   flag = 0
   break
  flag = 1
 return flag

for i in range(int(input())):
 ip = list(map(int, input().split()))

 pots = sum(ip)
 flag = 0
 cnt = 1
 while True:
  if isPrime(pots + cnt) == 1:
   print(cnt)
   break
  else:
   cnt += 1

# cook your dish here


# cook your dish here
import math


def isPrime(n):
 flag = 0
 for j in range(2, int(n)):
  if n % j == 0:
   flag = 0
   break
  flag = 1
 return flag

for i in range(int(input())):
 ip = list(map(int, input().split()))

 pots = sum(ip)
 flag = 0
 cnt = 1
 while True:
  if isPrime(pots + cnt) == 1:
   print(cnt)
   break
  else:
   cnt += 1



def primo(n):
 ctr=0
 for i in range(2,int(n**0.5)+1):
  if n%i==0:
   ctr=1
   break
 if ctr:
  return False
 else:
  return True
 

t=int(input())
for i in range(t):
 x,y=list(map(int,input().split()))
 j=1
 while primo(x+y+j)==False:
  j+=1
 print(j)
  
 


a=int(input())
for i in range (a):
 b,c=[int(b) for b in input().split()]
 for r in range (b+c+1,3001):
  s=0
  for t in range (2,r):
   if r%t==0:
    s+=1
  if s==0:
   print(r-b-c)
   break

# cook your dish here
T = int(input())

for i in range(0, T):
 (x,y) = map(int, input().split())
 z = x + y 
 Z = z + 1
 while Z != 0:
  for j in range(2, Z):
   if (Z % j) == 0:
    Z += 1 
    break
  else:
   break
 print(Z-z)

# cook your dish here
T = int(input())

for i in range(0, T):
 (x,y) = map(int, input().split())
 z = x + y 
 Z = z + 1
 while Z != 0:
  for j in range(2, Z):
   if (Z % j) == 0:
    Z += 1 
    break
  else:
   break
 print(Z-z)

# cook your dish here
T = int(input())

for i in range(0, T):
 (x,y) = map(int, input().split())
 z = x + y 
 Z = z + 1
 while Z != 0:
  for j in range(2, Z):
   if (Z % j) == 0:
    Z += 1 
    break
  else:
   b = Z
   Z = 0
   break
 print(b-z)

try:
 t = int(input())
 for i in range(t):
  a, b = map(int, input().split())
  c = a + b
  c1 = c + 1
  while c1 != 0:
   for j in range(2, c1):
    if (c1 % j) == 0:
     c1 += 1
     break
   else:
    c2 = c1
    c1 = 0
    break
  print(c2 - c)
except:
 pass

# cook your dish here
def check_prime(num):
 for i in range(2,num):

  if num%i==0:
   return ('Not Prime')

 else:
  return ('Prime')

t=int(input())
for i in range(t):
 n,m=list(map(int,input().split()))
 s=n+m
 if s%2==0:
  s+=1
  while check_prime(s)!='Prime':
   s+=2
   res= check_prime(s)
   if res=='Prime':
    print(s-n-m)
    break
  else:
   print(s-n-m)
 else:

  while True :
   s += 2
   res = check_prime(s)
   if res == 'Prime':
    print(s-n-m)
    break



def factors(n):
 c=0
 for i in range(1,n+1):
  if n%i==0:
   c+=1
 return c
 
t=int(input())
for _ in range(t):
 z=1
 x,y=map(int,input().split(" "))
 k=x+y
 while(True):
  t=k+z 
  if factors(t)==2:
   break
  else:
   z+=1
 print(z)
 t-=1

for _ in range(int(input())):
 x,y=list(map(int,input().split()))
 c=x+y
 n=1
 while(True):
  t=c+n
  for i in range(2,t):
   if t%i==0:
    break
  else:
   break
  n+=1
 print(n)
     


t=int(input())
for i in range(t):
 x,y=map(int,input().split())
 sum1=x+y+1
 sum2=sum1
 while(True):
  if sum1%2!=0:
   for j in range(3,sum1,2):
    if sum1%j==0:
     sum1+=2
     break
   else:
    print(sum1-sum2+1)
    break
  else:
   sum1+=1 

t=int(input())
for i in range(t):
 p1,p2=list(map(int,input().split()))
 num=p1+p2
 a=1
 

 while True:
  prime=num+a
  r=0
  for i in range(2,int(prime**0.5)+1):
   if prime%i==0:
    a+=1
    r=1
    break
  if r==0:
   print(a)
   break


  

  



t=int(input())
for i in range(t):
 p1,p2=list(map(int,input().split()))
 num=p1+p2
 a=1
 

 while True:
  prime=num+a
  r=0
  for i in range(2,int(prime**0.5)+1):
   if prime%i==0:
    a+=1
    r=1
    break
  if r==0:
   print(a)
   break


  

  



# cook your dish here
import math
for i in range(int(input())):
 x,y=map(int,input().split())
 sumi=x+y
 def isPrime(n): 
  if(n <= 1): 
   return False
  if(n <= 3): 
   return True
  if(n % 2 == 0 or n % 3 == 0): 
   return False
  for i in range(5,int(math.sqrt(n) + 1), 6):  
   if(n % i == 0 or n % (i + 2) == 0): 
    return False
  return True
 def nextPrime(N):  
  if (N <= 1): 
   return 2
 
  prime = N 
  found = False
 
 
  while(not found): 
   prime = prime + 1
 
   if(isPrime(prime) == True): 
    found = True
 
  return prime 
 
 print(nextPrime(sumi)-sumi)

# cook your dish here
def isprime(n):
 if (n<=3):
  return 1
 for i in range(2,int(n**0.5)+1):
  if(n%i==0):
   return 0
 else:
  return 1
t=int(input())
for i in range(t):
 x,y=map(int,input().split())
 z=x+y+1
 while(isprime(z)!=1):
  z+=1
 print(z-(x+y))

for _ in range(int(input())):
 x, y =list(map(int, input().split()))
 s = x + y
 n = 1
 while(True):
  t = s + n
  for i in range(2,t):
   if t%i == 0:
    break
  else:
   break
  n+=1
 print(n)