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: EASY
Tags: Mathematics

Number theory

Implementation

Complete search
Skill types: Complete search

Starter code:

Solutions:
t = int(input())
for i in range(t):
	(x, y) = map(int, input().split())
	a = x + y + 1
	b = 1
	while a > 0:
		for j in range(2, a - 1):
			if a % j == 0:
				break
		else:
			print(b)
			break
		a += 1
		b += 1


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(''))
c = 0
for i in range(1, t + 1):
	(x, y) = map(int, input().split())
	z = x + y
	while z > 0:
		z += 1
		for j in range(2, z):
			if z % j != 0:
				c += 1
		if c == z - 2:
			print(z - (x + y))
			z = -1
		c = 0


t = int(input())

def is_prime(numb):
	for i in range(2, numb):
		if numb % i == 0:
			return 0
	return 1
for i in range(t):
	(x, y) = map(int, input().split())
	z = 1
	sum = x + y + z
	while is_prime(sum) != 1:
		z += 1
		sum = x + y + z
	print(z)


n = 3000
nn = (n - 1) // 2
marked = [False] * (nn + 1)
marked[nn] = True
i = 1
while i <= nn:
	j = i
	while i + j + 2 * i * j <= nn:
		marked[i + j + 2 * i * j] = True
		j += 1
	i += 1
arr = []
for i in range(nn + 1):
	if marked[i] == False:
		arr.append(2 * i + 1)
t = int(input())
for i in range(t):
	su = sum(list(map(int, input().split())))
	st = 0
	ed = len(arr)
	while su >= arr[st]:
		mid = (st + ed) // 2
		if su >= arr[mid]:
			st = mid + 1
		else:
			ed = mid
	print(arr[st] - su)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	c = n + m
	k = 1
	c1 = True
	while True:
		for j in range(2, c + k):
			if (c + k) % j == 0:
				c1 = False
		if c1 == True:
			print(k)
			break
		c1 = True
		k = k + 1


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	z = x + y
	for i in range(z + 1, 2004):
		num = i
		flag = False
		for j in range(2, num):
			if num % j == 0:
				flag = True
				break
		if flag:
			continue
		else:
			print(num - z)
			break


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	c = x + y
	for i in range(1, 1000):
		c += 1
		for j in range(2, c):
			if c % j == 0:
				break
		else:
			print(i)
			break


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


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)


def check_prime(n):
	for i in range(2, int(n ** (1 / 2)) + 1):
		if n % i == 0:
			return True
	return False
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	i = 1
	while True:
		if check_prime(x + y + i):
			i += 1
		else:
			print(i)
			break


for i in range(int(input())):
	(x, y) = map(int, input().split())
	k = x + y + 1
	while k > 0:
		a = 0
		for i in range(1, k + 1):
			if k % i == 0:
				a += 1
		if a == 2:
			print(k - (x + y))
			break
		else:
			k = k + 1


def prime(a):
	ans = True
	for i in range(2, a):
		if a % i == 0:
			ans = False
			break
	return ans
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	z = 1
	while True:
		if prime(x + y + z):
			print(z)
			break
		z += 1


import math

def isPrime(n):
	if n <= 1:
		return False
	if n == 2:
		return True
	for i in range(2, math.ceil(math.sqrt(n)) + 1):
		if n % i == 0:
			return False
	return True
T = int(input())
for _ in range(T):
	(a, b) = map(int, input().split())
	c = 1
	while True:
		if isPrime(a + b + c):
			print(c)
			break
		c += 1


primes = [2]
for i in range(1, 2020, 2):
	for j in range(1, i // 2 + 1, 2):
		if i % j == 0 and j != 1:
			break
	else:
		primes.append(i)
for o in range(int(input())):
	s = sum(list(map(int, input().split()))) + 1
	primes.append(s)
	primes.sort()
	next = primes[primes.index(s) + 1]
	print(next - s + 1)
	primes.remove(s)


def prime(s):
	x = 0
	for i in range(3, s // 2):
		if s % i == 0:
			x = 1
			break
	if x == 0:
		return False
	return True
for i in range(int(input())):
	(a, b) = map(int, input().split())
	s = a + b + 1
	o = s - 1
	c = 1
	if s % 2 == 0:
		s = s + 1
	while prime(s):
		s += 2
	print(s - o)


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)


def is_prime(n):
	for i in range(2, n):
		if n % i == 0:
			return False
	return True
t = int(input())
for j in range(1, t + 1):
	(x, y) = [int(x) for x in input().split()]
	s = x + y
	for i in range(1, s + 1):
		s1 = s + i
		if is_prime(s1):
			print(i)
			break


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)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	z = x + y + 1
	a = 1
	s = 1
	while z > 0:
		for i in range(2, (z + 1) // 2 + 1):
			if z % i == 0:
				s = 0
				break
		else:
			print(a)
			break
		a += 1
		z += 1


def check_prime(num):
	for i in range(2, int(num ** 0.5 + 1)):
		if num % i == 0:
			return False
	return True
for i in range(int(input())):
	xandy = input().split()
	x = int(xandy[0])
	y = int(xandy[1])
	i = x + y + 1
	while i > x + y:
		if check_prime(i):
			print(i - (x + y))
			break
		else:
			i += 1


def isprime(num):
	for i in range(2, num):
		if num % i == 0:
			return 0
		else:
			continue
	else:
		return 1
for t in range(int(input())):
	(x, y) = map(int, input().split())
	num = x + y
	while True:
		num += 1
		if isprime(num) == 1:
			break
		else:
			continue
	print(num - x - y)


def f1(v):
	for i in range(2, v // 2 + 1):
		if v % i == 0:
			return False
	else:
		return True
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	v = n + k
	v1 = v + 1
	while True:
		if f1(v1) == True:
			print(v1 - v)
			break
		else:
			v1 += 1


def prime(n):
	for x in range(n + 1, 2 * n):
		cnt = 0
		for i in range(1, x // 2 + 1):
			if x % i == 0:
				cnt += 1
		if cnt == 1:
			return x
for _ in range(int(input())):
	(x1, x2) = map(int, input().split())
	p = prime(x1 + x2)
	print(p - x1 - x2)


def prime(n):
	if n == 1 or n == 0:
		return False
	if n == 2:
		return True
	for i in range(2, n // 2 + 1):
		if n % i == 0:
			return False
	return True
for i in range(int(input())):
	(x, y) = map(int, input().split())
	n = x + y
	while prime(n + 1) == False:
		n += 1
	print(n + 1 - x - y)


def isPrime(x, y, z):
	a = x + y + z
	flag = True
	for i in range(2, int(a / 2) + 1):
		if a % i == 0:
			flag = False
			break
	if flag:
		return True
	else:
		return False
for i in range(int(input())):
	(x, y) = list(map(int, input().split(' ')))
	z = 1
	while not isPrime(x, y, z):
		z = z + 1
	print(z)


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)


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))


def prime(x):
	c = 0
	for i in range(1, x + 1):
		if x % i == 0:
			c += 1
	if c == 2:
		return 'prime'
	else:
		return 'not'
for _ in range(int(input())):
	A = list(map(int, input().split()))
	i = sum(A) + 1
	f = 0
	while f == 0:
		if prime(i) == 'prime':
			f = -1
		i += 1
	print(abs(i - 1 - sum(A)))


def is_prime(num):
	for i in range(2, int(num / 2) + 1):
		if num % i == 0:
			return False
	else:
		return True
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	z = 1
	while True:
		if is_prime(sum([x, y, z])):
			print(z)
			break
		z += 1


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


abc = int(input())
for aaa in range(abc):
	(i, u) = map(int, input().split())
	bbb = i + u + 1
	cc = 1
	while bbb > 0:
		for kk in range(2, bbb - 1):
			if bbb % kk == 0:
				break
		else:
			print(cc)
			break
		bbb += 1
		cc += 1


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


from math import sqrt
for i in range(int(input())):
	(a, b) = map(int, input().split())
	c = a + b
	d = c
	while 1:
		count = 1
		d += 1
		for i in range(2, int(sqrt(d)) + 1):
			if d % i == 0:
				count = 0
				break
		if count == 1:
			print(d - c)
			break


t = int(input())
for i in range(t):
	(x, y) = map(int, input().split())
	i = 1
	while i > 0:
		c = 0
		for j in range(1, x + y + i):
			if (x + y + i) % j == 0:
				c += 1
		if c == 1:
			print(i)
			break
		else:
			i += 1


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


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 _ in range(T):
	(x, y) = map(int, input().split())
	final = 1
	s = x + y + 1
	while s > 0:
		for i in range(2, s - 1):
			if s % i == 0:
				break
		else:
			print(final)
			break
		s += 1
		final += 1


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 = input()
for c in range(0, int(t)):
	(wife, life) = map(int, input().split())
	aim = wife + life + 1
	final = 1
	while aim > 0:
		for j in range(2, aim - 1):
			if aim % j == 0:
				break
		else:
			print(final)
			break
		aim += 1
		final += 1


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


def is_prime(number):
	if number == 2 or number == 3:
		return True
	if number <= 1 or number % 2 == 0 or number % 3 == 0:
		return False
	for x in range(5, int(number ** 0.5) + 1, 2):
		if not number % x:
			return False
	return True
for _ in range(int(input())):
	(x, y) = map(int, input().split())
	for i in range(1, 100):
		if is_prime(x + y + i):
			print(i)
			break
	else:
		print(1)


t = int(input())
for i in range(t):
	(x, y) = map(int, input().split())
	s = x + y
	temp = 0
	fin = 0
	for j in range(1, 1000):
		temp = s + j
		for k in range(2, temp):
			if temp % k == 0:
				break
		else:
			fin = j
			break
	print(fin)


def isprime(x):
	i = 2
	while i < x:
		if x % i == 0:
			return False
		i += 1
	return True

def check(x):
	c = 1
	while not isprime(c + x):
		c += 1
	print(c)
t = int(input())
for i in range(t):
	(x, y) = list(map(int, input().split()))
	check(x + y)


def isprime(x, y, z):
	a = x + y + z
	for i in range(2, a):
		if a % i == 0:
			return 0
	else:
		return 1
t = int(input())
for i in range(t):
	(x, y) = map(int, input().split())
	j = 1
	while 10:
		if isprime(x, y, j) == 1:
			print(j)
			break
		else:
			j += 1


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)


def isprime(a):
	if a == 3:
		return True
	for i in range(2, a):
		if a % i == 0:
			return False
	return True
for tc in range(int(input())):
	(a, b) = map(int, input().split())
	num = a + b
	i = 1
	while i != 0:
		if isprime(num + i):
			print(i)
			break
		else:
			i += 1


for i in range(int(input())):
	(x, y) = map(int, input().split())
	t = x + y
	z = x + y
	while True:
		sum = 0
		t = t + 1
		for i in range(2, t):
			if t % i == 0:
				sum = sum + 1
		if sum == 0:
			print(t - z)
			break


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


from math import sqrt
T = int(input())

def is_prime(n):
	prime_flag = 0
	if n > 1:
		for i in range(2, int(sqrt(n)) + 1):
			if n % i == 0:
				prime_flag = 1
				break
		if prime_flag == 0:
			return True
		else:
			return False
	else:
		return False
for i in range(T):
	(x, y) = map(int, input().split())
	tot = x + y
	for j in range(1, tot):
		if is_prime(tot + j) == True:
			print(j)
			break


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)


l = []
for number in range(1, 2004):
	if number > 1:
		for i in range(2, number):
			if number % i == 0:
				break
		else:
			l.append(number)
for k in range(int(input())):
	(x, y) = map(int, input().split())
	for i in l:
		if x + y < i:
			break
	print(i - (x + y))


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


def check(val):
	c = 0
	for i in range(2, val // 2 + 1):
		if val % i == 0:
			c += 1
			break
	if c == 0:
		return 1
	else:
		return 0
t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	z = 1
	while True:
		if check(a + b + z):
			break
		else:
			z += 1
	print(z)


for i in range(int(input())):
	(a, b) = map(int, input().split())
	x = a + b
	c = 0
	g = 0
	co = 0
	while c == 0:
		for j in range(2, 100):
			if (x % j == 0 or co == 0) and j != x:
				g = 1
				break
		if g == 1:
			x += 1
			co += 1
			g = 0
		else:
			print(co)
			c = 1


def prime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			break
	else:
		return True
t = int(input())
for i in range(t):
	a = list(map(int, input().split()))
	b = sum(a)
	for i in range(1, 100):
		if prime(b + i):
			print(i)
			break


for i in range(int(input())):
	x = list(map(int, input().split()))
	c = 0
	for i in x:
		c = c + i
	v = 1
	b = 1
	h = 0
	while 1:
		c = c + b
		v = 0
		n = 0
		for i in range(2, c):
			if c % i != 0:
				v = 0
			else:
				n = 1
		h = h + 1
		if n == 0:
			break
	print(h)


t = int(input())
while t != 0:
	(x, y) = map(int, input().split())
	s = x + y + 1
	if s % 2 == 0:
		s += 1
	while True:
		c = 0
		f = 2
		while f <= s / 2:
			if s % f == 0:
				c = 1
				break
			f += 1
		if c == 0:
			break
		else:
			s += 2
	print(s - (x + y))
	t -= 1


def prime(n):
	c = 0
	for i in range(1, n + 1):
		if n % i == 0:
			c += 1
	if c == 2:
		return 1
	else:
		return 0
n = int(input())
for i in range(n):
	(a, b) = map(int, input().split())
	y = a + b
	c = 1
	for i in range(y + 1, 10001):
		if prime(i) == 1:
			print(c)
			break
		else:
			c += 1


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))


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


for j in range(int(input())):
	(x, y) = map(int, input().split())
	s = x + y

	def isprime(n):
		for i in range(2, n):
			if n % i == 0:
				return 0
			else:
				continue
		else:
			return 1
	while True:
		s += 1
		if isprime(s) == 1:
			break
		else:
			continue
	print(s - x - y)


for i in range(int(input())):
	(x, y) = map(int, input().split())
	count = 1
	flag = 0
	while True:
		ans = x + y + count
		c = 0
		for i in range(1, ans):
			if ans % i == 0:
				c += 1
		if c == 1:
			break
		else:
			count += 1
	print(count)


import math
t = int(input())

def isprime(n):
	stat = True
	for i in range(2, int(math.sqrt(n)) + 1):
		if n % i == 0:
			stat = False
			break
	return stat
for _ in range(t):
	(x, y) = map(int, input().split())
	init = x + y + 1
	cond = True
	while cond:
		if isprime(init) == True:
			print(init - x - y)
			break
		else:
			init += 1


from math import sqrt
for a0 in range(int(input())):
	(x, y) = map(int, input().split())
	z = x + y
	i = 1
	ctr = 1
	while True:
		z += i
		for j in range(2, int(sqrt(z)) + 1):
			if z % j == 0:
				break
		else:
			print(ctr)
			break
		ctr += 1


def prime(n):
	for i in range(2, n):
		if n % i == 0:
			return False
	return True
t = int(input())
while t:
	(x, y) = map(int, input().split())
	sm = x + y + 1
	while True:
		if prime(sm):
			break
		sm += 1
	print(sm - x - y)
	t -= 1


t = int(input())
for tc in range(t):
	(x, y) = map(int, input().split())
	s = x + y + 1
	b = 1
	while s > 0:
		for j in range(2, s - 1):
			if s % j == 0:
				break
		else:
			print(b)
			break
		b += 1
		s += 1


t = int(input())

def prime(val):
	if val < 2:
		return 0
	elif val == 2:
		return 1
	else:
		for i in range(2, int(val ** 0.5) + 1):
			if val % i == 0:
				return 0
		return 1
for _ in range(t):
	(a, b) = tuple(map(int, input().split()))
	z = a + b + 1
	while prime(z) != 1:
		z += 1
	print(z - a - b)


goals = int(input())
for distractions in range(goals):
	(wife, life) = map(int, input().split())
	aim = wife + life + 1
	final = 1
	while aim > 0:
		for j in range(2, aim - 1):
			if aim % j == 0:
				break
		else:
			print(final)
			break
		aim += 1
		final += 1