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.


hide comments
[Lakshman]: 2021-07-08 05:52:19

@@sgtlaugh Can you please verify all submissions by CRV college? all seems to be the same.

[NG]: sgtlaugh, please take log of users from that school who cheated on your problem again, I can see them doing it elsewhere too and will contact admins about this, thanks.

-> Yes they are cheating. Looks like they're already banned here.

Last edit: 2021-09-02 18:54:04
weathervane: 2020-09-17 15:57:31

Strange. I took 12% off the run time of my big test file at home, yet it took longer than my first submission.

(sgtlaugh): That's probably because the runtime of your codes can vary and depends a lot on the compiler, platform, architecture, etc.

Last edit: 2020-11-06 22:27:18
singhsauravsk: 2016-10-03 13:04:11

@sgtlaugh : could you please give a test case where my submission number 17841013 gives TLE.

(sgtlaugh): You are ignoring the fact that T can be as large as 10^6. Try giving the cases mentioned in the comments below 10^6 times and your code should time out.

Last edit: 2019-02-28 22:38:44
luoji83: 2016-03-03 18:16:32

Is T (number of trials) really as high as 1,000,000? Using what I thought was a fast palindrome generator and Miller Rabin primality test, it's still between 5-10 seconds per computation for random 13-digit numbers:

working on 8572115172675
7499982899947
working on 5127997788693
3899960699983
working on 440780157081
99999199999
working on 6546887935149
3899960699983
...

@sgtlaugh: is a mathematical insight needing to be found? or can this all optimization be done algorithmically?

(sgtlaugh): Yes the number of test cases can be as high as 1,000,000. A little mathematical insight and some observations are required but most of the optimization can be done algorithmically. Oh and your output is wrong for 8572115172675, 5127997788693 and 6546887935149.

Last edit: 2016-03-04 13:52:10
[Lakshman]: 2016-03-01 09:39:35

@sgtlaugh can this be done without pre-computation?
(sgtlaugh): This can be solved without hard coding a table of pre-computed values if that's what you mean.

Last edit: 2016-03-01 15:14:52
it_is_me: 2016-02-27 18:12:58

Optimized my algorithm yet got tle help somebody
(sgtlaugh): You cannot get Accepted with such a naive approach.

can you please tell me what is my execution time?
(sgtlaugh): 100 billion years

Last edit: 2016-02-28 22:52:10
chiragm23: 2016-02-26 21:10:04

@Blue Mary,i am getting WA.Could u plz provide some more test cases so i can figure out my mistake??

it_is_me: 2016-02-26 15:28:42

@Blue.Mary any help on algorithm which part to improve please
getting tle

Last edit: 2016-02-26 15:31:22
[Rampage] Blue.Mary: 2016-02-26 12:39:50

@sgtlaugh, I've optimized my code a little, never mind :-)

Scape: 2016-02-26 12:38:57

@Blue Mary, your first submission gets Accepted instead of TLE with C++ 5


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