Composite Prime

$1313$ factors as $13 \times 101$, so it is composite. However, every proper contiguous subnumber of $1313$ made from at least two consecutive digits, namely $13$, $31$, $13$, $131$, and $313$, is prime.

For a positive integer $N$ with at least three digits, define a proper contiguous subnumber as follows. Take two or more consecutive digits from the decimal representation of $N$, keep their order, and interpret the result as a nonnegative integer. The number $N$ itself is excluded.

A positive integer $N$ is called a composite prime if all three conditions below hold.

• $N$ has at least three digits.
• $N$ is composite.
• Every proper contiguous subnumber of $N$ is prime.

A proper contiguous subnumber may start with $0$, and the value $0$ itself is possible. For example, the proper contiguous subnumbers of $20023$ include $20$, $00(=0)$, $02(=2)$, $23$, $200$, $002(=2)$, $023(=23)$, $2002$, and $0023(=23)$. Since $20$ is not prime, $20023$ is not a composite prime.

Given a positive integer $N$, find the largest composite prime not greater than $N$.

The first line contains the number of test cases $T$. $(1 \le T \le 10^5)$

Each of the next $T$ lines contains one integer $N$. $(1 \le N \le 10^7)$

For each test case, print the largest composite prime not greater than $N$ on its own line. If no such number exists, print $-1$ instead.

Print the answers in the same order as the input test cases.