SPOJ.com - Problem POP1

POP1 - play with prime numbers (I)

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

We define here a new prime number called prime of primes number (POP) is a prime number that consist of other prime numbers less than this number.

For example: 1013 consist of 101 and 3 and both are primes.

Note: 2003 is not POP because leading zero not allowed.

The POP number must contain more than or equal two primes , and overlapping not allowed.

Input

The first line contains an integer T specifying the number of test cases. (T <= 10^4) followed by T lines, each line contains an integer m number 0 <= m <= 10^9.

Output

For each test case print single line contain the first integer greater than or equal to m and is POP.

Example

Input:
3
10
100
1000

Output:
23
113
1013

after solving this you can try http://www.spoj.com/problems/POP2/

Submit solution!

Added by:	abdou_93
Date:	2013-06-05
Time limit:	2s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64
Resource:	owner

hide comments

2020-04-02 19:55:37 David
Awesome problem

2018-01-13 16:10:51 [Lakshman]
@sonu1801 because 1012 is not a prime number.

2018-01-13 12:59:21
can anybody explain why 1012 is not solution of 1000 (101+2)

2013-06-10 06:11:34 Mitch Schwartz
@fitcat: [snip]

Sorry, I thought I knew an easy way to batch disqualify all submissions from a given account (if that's what you are doing), but my idea was wrong, so I removed it. The problem is that you can only view the first 5 pages of submission history, or 100 most recent submissions (actually you can get the 6th page too, but not more than 6). So after that the only way might be to do it on a problem-by-problem basis, i.e. http://www.spoj.com/status/PROBCODE,username/ for each problem.

Edit: Thanks for your consideration. Of course solving in the main problem set is different from participating in a live contest and the points/rankings may be thought of differently between the two, but I think it's still good to keep the number of solvers/point value for classical problems as accurate as possible (especially for harder problems), and your actions in this regard have been admirable.

Last edit: 2013-06-10 12:51:40

2013-06-10 05:42:32 fitcat
@abdelkarim: I am not aware I can do this. I will disqualify all of them. Sorry for everyone.-

Edit: Done (really tedious).

Last edit: 2013-06-10 06:30:32

2013-06-10 03:29:56 abdelkarim
@fitcat
please disqualify your solutions in other account .

Last edit: 2013-06-10 03:33:10

2013-06-10 03:14:11 fitcat
@Mitch: I use the 2nd account mainly to help people in the forum. Verified what they said by submitting their code. Tried to figure out the problem. Make sure the correctness by submitting the modified code until AC. Finally, gave them hints. I encountered one claiming WA but in fact getting AC without changes. I don't want this kind of activities "pollute" my real account.

I also used it to do input validity check, try optimization with other algorithms, use of other programming languages, implement proof of concept, etc.

Sometimes, I just forget to switch back to my real account.

Yes, I do know it affect the points I get (and others). I don't care much about points. Sorry for those who care.

2013-06-08 13:59:10 Mitch Schwartz
@fitcat: You know that solving a classical problem with two accounts makes it worth less points, right? (It doesn't matter if one of the accounts is excluded from global rank list.)

2013-06-07 05:47:41 fitcat
@abdelkarim: What I want to say is that the definition is not clear. Without the notes section, is the current definition precise enough? Surely not. Hence, the conditions in the notes section have to be included into the definition.

2013-06-06 17:07:19 abdelkarim
@fitcat :
"less than this number" is a part of the definition , but the notes section was added to make the problem more clear .