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

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.

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