xenny-and-composite-number
Source: hackerearth
Difficulty: UNKNOWN_DIFFICULTY

Today, teacher taught Xenny the chapter 'Prime numbers and Composite numbers'. Xenny liked it and being a studious boy, wanted some homework. So teacher gave him a simple task. The task is to find the smallest composite number greater than given no. Xenny was happy to get the simple task. But Xenny didn't get the time for complting the homework being busy in helping his mother throughout the day. You, a best friend of Xenny, don't want Xenny to get punished by teacher. So its your job to complete his homework.
Formally, there will be t numbers and you have to find smallest greater composite number for each of them.

Input:

The first line of input will be t i.e. number of test-cases.
Followed by t lines each containing n.

Output:

For each test-case, Print the smallest greater number than n which is a composite number on new line.

Constraints:

SMALL:

1 ≤ t ≤ 10

0 ≤ n ≤ 10

MEDIUM:

1 ≤ t ≤ 500

0 ≤ n ≤ 1000

LARGE:

1 ≤ t ≤ 50000

0 ≤ n ≤ 100000

SAMPLE INPUT
2
3
8

SAMPLE OUTPUT
4
9

Explanation

Test-cases are 2.
For first case, the smallest composite no. greater than 3 is 4 .
For second case, the smallest composite no. greater than 8 is 9 .


def isprime(n):
	for i in range(2,int(n**0.5)+1):
		if n%i==0:
			return False
	return True
for p in range(eval(input())):
	x=eval(input())
	for i in range(x+1,x+10):
		if isprime(i):
			continue
		else:
			print(i)
			break
	


def isprime(n):
	for x in range(2, int(n**0.5)+1):
		if n % x == 0:
			return False
	return True
t=eval(input())
while(t):
		n=eval(input())
		flag=1
		i=n+1
		while(flag):
				if not isprime(i):
						print(i)
						flag=0
				else:
						i+=1
		t-=1


def isPrime(n):
	for i in range(3,int(n**0.5) + 1):
		if n%i==0:
			return False
	return True


for i in range(eval(input())):
	num = eval(input())
	if num<4:
		print(4)
	elif num%2==1:
		print(num+1)
	else:
		if isPrime(num+1):
			print(num+2)
		else:
			print(num+1)


def _try_composite(a, d, n, s):
	if pow(a, d, n) == 1:
		return False
	for i in range(s):
		if pow(a, 2**i * d, n) == n-1:
			return False
	return True # n  is definitely composite

def is_prime(n, _precision_for_huge_n=16):
	if n in _known_primes or n in (0, 1):
		return True
	if any((n % p) == 0 for p in _known_primes):
		return False
	d, s = n - 1, 0
	while not d % 2:
		d, s = d >> 1, s + 1
   
	if n < 1373653:
		return not any(_try_composite(a, d, n, s) for a in (2, 3))
	if n < 25326001:
		return not any(_try_composite(a, d, n, s) for a in (2, 3, 5))
	if n < 118670087467:
		if n == 3215031751:
			return False
		return not any(_try_composite(a, d, n, s) for a in (2, 3, 5, 7))
	if n < 2152302898747:
		return not any(_try_composite(a, d, n, s) for a in (2, 3, 5, 7, 11))
	if n < 3474749660383:
		return not any(_try_composite(a, d, n, s) for a in (2, 3, 5, 7, 11, 13))
	if n < 341550071728321:
		return not any(_try_composite(a, d, n, s) for a in (2, 3, 5, 7, 11, 13, 17))
	# otherwise
	return not any(_try_composite(a, d, n, s)
				   for a in _known_primes[:_precision_for_huge_n])

_known_primes = [2, 3]
_known_primes += [x for x in range(5, 1000, 2) if is_prime(x)]

for i in range(eval(input())):
	a = eval(input())
	
	while True:
		a+=1
		if not is_prime(a):
			print(a)
			break


import math
primelist=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199]
skiplist=[1,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,179,191,193,197,199]

def isprime(p):
#    print p
	i=0
	temp=math.sqrt(p)
#    print temp
	while(primelist[i]<temp):
#        print primelist[i]
		if(p%primelist[i]==0):
			break
		else:
			i=i+1
	if(primelist[i]>temp):
#        primelist.append(p)
		return 1
	else:
		return 0


for i in range(1,3):
	for j in range(0,43):
		temp=210*i+skiplist[j]
		if(isprime(temp)):
			primelist.append(temp)
#            print temp

#print primelist
for z in range(int(input())):
	n=int(input())+1
	if n==2 or n==1:
		print("4")
	elif(isprime(n)):
		print(n+1)
	else:
		print(n)