MB1  PP numbers
PP numbers are prime numbers and palindromes in decimal notation at once. Your task is to find nth PP number in ascending order. Then calculate product of its nonzero digits  let's call it m  and find mth 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: nth PP number and mth prime number.
Example
Input:
3 1 5 2
Output:
2 3 11 2 3 5
hide comments
Francky:
20130113 22:40:25
Warning : input seems badly formated. But, I don't know where is the problem.


Snehasish Roy ;):
20130113 21:50:36
:D


Man Mohan Mishra:
20130103 18:14:19
really nice problem !! :) 

Blasters:
20121219 19:55:29
can anyone pl tell the 113 pp no is it 98***


Erik LonĂ¨arek:
20121208 17:01:21
@Anmol Have you considered input 113? Perhaps you should use long long. 

Nic Roets:
20120310 20:27:16
@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. 

Anmol:
20120131 22:03:35
all precalculations correct but gettin wa


Hafidh S.A:
20111223 01:27:35
@sid


sandeep pandey:
20110130 23:07:25
phew!AC:)) Last edit: 20110210 12:50:38 

sid:
20110112 20:37:41
all possible test cases must be from 1 to 113??....i have checked all d test cases...thn also its shown wrong ovr here 
Added by:  Maciej Boniecki 
Date:  20100402 
Time limit:  0.5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 
Resource:  2nd Warsaw School of Computer Science Programming Championship 