A:It is a natural number greater than 1 that has no positive divisors other than 1 and itself.

B: It is a number  that remains the same when its digits are reversed. It is "symmetrical". 

Patrik lives in Palestine. He loves everything starting with P and so numbers also. His friend gave him a number X and asked him to find smallest integer say Y where, Y ≥ X such that Y is a A and B type number. You task is to Help Patrik to find required number Y every time.   

Input format:
First line of input contains an integer t, which is the number of test cases. t lines follow, with each test containing an integer X.

Output format:
For each test case output a single line number Y which is of type A and B both.

Constraints:
1 ≤ X ≤ 1000000

1 ≤ t ≤ 100

NOTE:
A and B are a type of number.  Read definition statement properly if you are not getting.

SAMPLE INPUT
3
42
108
250

SAMPLE OUTPUT
101
131
313

Explanation

101 is the smallest number prime number which is palindrome also after 42.
Similarly all the cases have respective output on provided input.
p=[1 , 1 , 2 , 3 , 5 , 7 , 11 , 101 , 131 , 151 , 181 , 191 , 313 , 353 , 373 , 383 , 727 , 757 , 787 , 797 , 919 , 929 , 10301 , 10501 , 10601 , 11311 , 11411 , 12421 , 12721 , 12821 , 13331 , 13831 , 13931 , 14341 , 14741 , 15451 , 15551 , 16061 , 16361 , 16561 , 16661 , 17471 , 17971 , 18181 , 18481 , 19391 , 19891 , 19991 , 30103 , 30203 , 30403 , 30703 , 30803 , 31013 , 31513 , 32323 , 32423 , 33533 , 34543 , 34843 , 35053 , 35153 , 35353 , 35753 , 36263 , 36563 , 37273 , 37573 , 38083 , 38183 , 38783 , 39293 , 70207 , 70507 , 70607 , 71317 , 71917 , 72227 , 72727 , 73037 , 73237 , 73637 , 74047 , 74747 , 75557 , 76367 , 76667 , 77377 , 77477 , 77977 , 78487 , 78787 , 78887 , 79397 , 79697 , 79997 , 90709 , 91019 , 93139 , 93239 , 93739 , 94049 , 94349 , 94649 , 94849 , 94949 , 95959 , 96269 , 96469 , 96769 , 97379 , 97579 , 97879 , 98389 , 98689 , 1003001]

for _ in xrange(input()): 
	n=input()
	for i in p:
	    if i>=n:
	        break
	print i