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

2013-06-06 17:07:19 fitcat
@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.

2013-06-06 17:07:19 Mitch Schwartz
@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.)

2013-06-06 17:07:19 abdou_93
@Robert Gerbicz.. congratulation you the first one

2013-06-06 17:07:19 Francky
@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

2013-06-06 17:07:19 fitcat
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

2013-06-06 17:07:19 fitcat
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

2013-06-06 17:07:19 abdou_93
@Robert Gerbicz...the Problem in Cluster Pyramid (Intel Pentium III 733 MHz) not me..