PALPRIM - Palindromic Primes (Hard)

A Palindromic number is a number without leading zeros that remains the same when its digits are reversed. For instance 5, 22, 12321, 101101 are Palindromic numbers where as 10, 34, 566, 123421 are not. A Prime number is a positive integer greater than 1 that has no positive divisors other than 1 and itself. For example, 2, 31, 97 are Prime numbers but 1, 10, 25, 119 are not. A Palindromic Prime number is both palindromic and prime at the same time. 2, 3, 131 are Palindromic Prime numbers but 6, 17, 3333 are not. Given a positive integer N, output the largest palindromic prime number not greater than N

Input

The first line contains an integer T denoting the number of test cases. Each of the subsequent T lines contain a single integer N without leading/trailing spaces. 

Output

Print T lines. For each test case, print a single integer denoting the largest palindromic prime number which does not exceed N. 

Constraints

1 ≤ T ≤ 10^6

≤ N ≤ 10^13

Example

Input:
3
2
10
666

Output:
2
7
383

Note Large input and output, please use faster I/O methods.


Added by:sgtlaugh
Date:2016-02-26
Time limit:15s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:Own Problem

hide comments
2016-02-26 10:24:09 Min_25
Please clarify the constraints on T and N.

ANS: Sure, just one moment.
UPD: Done, sorry for the delay. I had trouble uploading the input and output files.

(Re) Thank you!

Last edit: 2016-02-26 14:01:42
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.