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

hide comments
pratham_1: 2017-07-16 19:28:04

AC in one go:) precomputation is the key , my 5th AC:)

sri: 2016-11-21 18:28:31

Must try test cases
5
6
110
111
112
113

Output :
101 2
97579 222863
97879 373019
98389 170627
98689 364523

ani_geek9654: 2016-10-10 17:59:26

EASY AC IN ONE :)

Sarthak Munshi: 2016-09-12 10:48:54

are single digit primes considered a palindrome ?

karan_batra: 2016-08-28 14:57:00

AC in one go. Easy one :D

vikikkdi: 2016-07-06 18:13:14

precomputation and o(1) retrieval

akshayvenkat: 2016-07-02 20:09:29

there is still some problem with the input files, sir. my precomputation solution gave WAs, while predefined array solution gave AC.. why?

Vars: 2016-05-14 12:02:24

precomputation and u r done!! :)

Mayank Garg: 2015-12-19 11:57:49

Easy one ... My 250th green !! :-)

Maciej Boniecki: 2015-11-15 14:55:35

There was additional empty line at the end of first input file. It was removed. Now all of input files are correct.


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