Smallest Prime Palindrome

You are given an integer \(N\). Your task is to find the smallest integer strictly greater than \(N\) that is both a prime number and a palindrome.

A number is a palindrome if it reads the same forwards and backwards (e.g. 121, 22). A prime number is an integer greater than 1 that has no proper divisors other than 1 and itself.

It is guaranteed that for the given constraints, such a number always exists.

inputFormat

The first line contains a single integer \(T\), the number of test cases.

Then \(T\) lines follow, each containing one integer \(N\).

\(1 \leq T \leq 1000\) and \(0 \leq N \leq 10^6\) (for instance).

outputFormat

For each test case, output the smallest prime palindrome greater than \(N\) on a new line.

## sample

3
13
31
100

101
101
101

</p>