SPOJ.com - Problem PALPRIM

PALPRIM - Palindromic Primes (Hard)

#binary-search #primality-test #precalculation

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

2 ≤ N ≤ 10^13

Example

Input:
3
2
10
666

Output:
2
7
383

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

Submit solution!

hide comments

< Previous 1 2 Next >

	[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

Submit solution!

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