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
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.