MB1 - PP numbers

PP numbers are prime numbers and palindromes in decimal notation at once. Your task is to find n-th PP number in ascending order. Then calculate product of its non-zero digits - let's call it m - and find m-th prime number in ascending order.

Input

In the first line of input there is one positive integer Z (1 ≤ Z ≤ 1000) which states the number of test cases. Following Z lines contain test cases.

Each test case consists of one positive integer n (1 ≤ n ≤ 113) which states the number of PP number to find.

Output

For each test case print in separate line two numbers: n-th PP number and m-th prime number.

Example

Input:
3
1
5
2

Output:
2 3
11 2
3 5

Added by:Maciej Boniecki
Date:2010-04-02
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:2nd Warsaw School of Computer Science Programming Championship

hide comments
2012-12-19 19:55:29 Blasters
can anyone pl tell the 113 pp no is it 98***


Last edit: 2012-12-19 19:56:48
2012-12-08 17:01:21 Erik Lonèarek
@Anmol Have you considered input 113? Perhaps you should use long long.
2012-03-10 20:27:16 Nic Roets
@vivek Let's say approximately 1 in 10 numbers are prime. Then you will need 1130 palindromes. From combinatorics we know that there are 900 palindromes with 5 digits and another 900 with 6 digits. So 5 or 6 digits is a good guess.
2012-01-31 22:03:35 Anmol
all precalculations correct but gettin wa
please help wid sum i/o

Last edit: 2012-01-31 22:04:52
2011-12-23 01:27:35 Hafidh S.A
@sid
i get same problem with you. any one can tell me
2011-01-30 23:07:25 sandeep pandey
phew!AC:))

Last edit: 2011-02-10 12:50:38
2011-01-12 20:37:41 sid
all possible test cases must be from 1 to 113??....i have checked all d test cases...thn also its shown wrong ovr here
2011-01-12 01:55:25 vivek yadav
plz provide 113 pp number..
how many digit it have????
2011-01-08 12:23:02 The Bartender
maybe EndOfLine: \r\n

Last edit: 2011-06-18 09:07:13
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.