POP3 - play with prime numbers (III)(hard )

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.

example:

1013 consist of 101 and 3 and both are primes.

notes:

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 <= 200) followed by T lines, each line contains an integer m number 0 <=m <= 10^27.

Output

For each test case, print a single line containing the first integer greater than or equal to m and is (POP).

Example

```Input:
3
10
100
1000

Output:
23
113
1013```

Code Examples

#1 Code Example with Python Programming

```Code - Python Programming```

``````import random

_mrpt_num_trials = 5  # number of bases to test

def is_probable_prime(n):
"""
Miller-Rabin primality test.

A return value of False means n is certainly not prime. A return value of
True means n is very likely a prime.

>>> is_probable_prime(1)
Traceback (most recent call last):
...
AssertionError
>>> is_probable_prime(2)
True
>>> is_probable_prime(3)
True
>>> is_probable_prime(4)
False
>>> is_probable_prime(5)
True
>>> is_probable_prime(123456789)
False

>>> primes_under_1000 = [i for i in range(2, 1000) if is_probable_prime(i)]
>>> len(primes_under_1000)
168
>>> primes_under_1000[-10:]
[937, 941, 947, 953, 967, 971, 977, 983, 991, 997]

>>> is_probable_prime(6438080068035544392301298549614926991513861075340134\
3291807343952413826484237063006136971539473913409092293733259038472039\
7133335969549256322620979036686633213903952966175107096769180017646161\
851573147596390153)
True

>>> is_probable_prime(7438080068035544392301298549614926991513861075340134\
3291807343952413826484237063006136971539473913409092293733259038472039\
7133335969549256322620979036686633213903952966175107096769180017646161\
851573147596390153)
False
"""
if n < 2:
return False
# special case 2
if n == 2:
return True
# ensure n is odd
if n % 2 == 0:
return False
# write n-1 as 2**s * d
# repeatedly try to divide n-1 by 2
s = 0
d = n - 1
while True:
quotient, remainder = divmod(d, 2)
if remainder == 1:
break
s += 1
d = quotient
assert (2 ** s * d == n - 1)

# test the base a to see whether it is a witness for the compositeness of n
def try_composite(a):
if pow(a, d, n) == 1:
return False
for i in range(s):
if pow(a, 2 ** i * d, n) == n - 1:
return False
return True  # n is definitely composite

for i in range(_mrpt_num_trials):
a = random.randrange(2, n)
if try_composite(a):
return False

return True  # no base tested showed n as composite

def check(N):
N = str(N)
l = len(N)
dp = [-1 for i in range(l)]
for i in range(l):
if is_probable_prime(int(N[0 : i + 1])):
dp[i] = 1
for i in range(l):
for j in range(1, i + 1):
if dp[j - 1] != -1 and N[j] != '0' and dp[j - 1] + 1 > dp[i]:
if is_probable_prime(int(N[j : i + 1])):
dp[i] = dp[j - 1] + 1
if dp[l - 1] > 1:
return True
return False

T = int(raw_input())
for i in range(T):
N = int(raw_input())
while is_probable_prime(N) == False or check(N) == False:
N = N + 1
print(N)``````
Copy The Code &

Input

cmd
3
10
100
1000

Output

cmd
23
113
1013