SP26450 PALPRIM - Palindromic Primes (Hard)

A Palindromic number is a number without leading zeros that remains the same when its digits are reversed. For instance **5, 22, 12321, 101101** are Palindromic numbers where as **10, 34, 566, 123421** are not. A Prime number is a positive integer greater than **1** that has no positive divisors other than **1** and itself. For example, **2, 31, 97** are Prime numbers but **1, 10, 25, 119** are not. A Palindromic Prime number is both palindromic and prime at the same time. **2, 3, 131** are Palindromic Prime numbers but **6, 17, 3333** are not. Given a positive integer **N**, output the largest palindromic prime number not greater than **N**.

The first line contains an integer **T** denoting the number of test cases. Each of the subsequent **T** lines contain a single integer **N** without leading/trailing spaces.

Print **T** lines. For each test case, print a single integer denoting the largest palindromic prime number which does not exceed **N.** ### Constraints **1 T** **2 N**