SPOJ.com - Problem POP1

POP1 - play with prime numbers (I)

#primality-test

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!

hide comments

< Previous 1 2 Next >

	fitcat: 2013-06-06 17:07:19 @Mitch: As said in the notes section, POP must consist of 2 or more distinct prime numbers. The condition "less than this number" is irrelevant, I believe. I think it is required when the notes section is not there when this problem first appeared. With the notes section added, the statement should change accordingly.
	Mitch Schwartz: 2013-06-06 17:07:19 @fitcat: For example in explaining the answer for 10 being 23: 2 and 3 are both less than 23. (We do not care whether or not 2 and 3 are less than 10.)
	abdou_93: 2013-06-06 17:07:19 @Robert Gerbicz.. congratulation you the first one
	Francky: 2013-06-06 17:07:19 @psetter : please explain what was the problem with pyramid cluster ; it's so curious. (abdou)-->by pyramid cluster the code give me runtime error (SIGSEGV) ..but by Cube cluster give me accepted --(francky)--> But you should know that's the fault is yours, not pyramid's ! A well designed program should work with both. So I'm not sure you have good IO files... ans(gerrob):Solved the problem, the io is good. Last edit: 2013-06-05 14:45:17
	fitcat: 2013-06-06 17:07:19 In the POP's definition, what does "less than this number" means? For m = 0 to 3, there are no 2 distinct prime numbers that are less than m (abdou)-->less than itself (prime number not m) Edit: Would you please give us a counter example that is not less than itself? (abdou)-->like 2 is prime number and consist of 2 (prime).but 2 not POP Edit: But 2 is not consists of 2 distinct prime numbers. Last edit: 2013-06-05 14:37:49
	fitcat: 2013-06-06 17:07:19 When m = 100, why the answer is not 112? (abdou)-->112 is not prime Edit: Thanks. I overlooked it. Last edit: 2013-06-05 13:44:10
	abdou_93: 2013-06-06 17:07:19 @Robert Gerbicz...the Problem in Cluster Pyramid (Intel Pentium III 733 MHz) not me..

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