합성소수

$1313$은 $13 \times 101$로 소인수분해되므로 합성수이다. 그러나 $1313$에서 연속한 두 자리 이상을 골라 만든 자기 자신이 아닌 수 $13$, $31$, $13$, $131$, $313$은 모두 소수이다.

이 문제에서 세 자리 이상의 양의 정수 $N$에 대해 연속 부분수를 다음과 같이 정의한다. $N$의 십진수 표현에서 연속한 2개 이상의 숫자를 선택하고, 순서를 유지해 만든 수 중 $N$ 자신을 제외한 음이 아닌 정수이다.

양의 정수 $N$이 다음 세 조건을 모두 만족하면 합성소수라고 부른다.

• $N$은 세 자리 이상이다.
• $N$은 합성수이다.
• $N$의 모든 연속 부분수가 소수이다.

연속 부분수는 $0$으로 시작할 수 있으며, $0$ 자체도 가능한 값으로 다룬다. 예를 들어 $20023$의 연속 부분수에는 $20$, $00(=0)$, $02(=2)$, $23$, $200$, $002(=2)$, $023(=23)$, $2002$, $0023(=23)$이 포함된다. 이 중 $20$은 소수가 아니므로 $20023$은 합성소수가 아니다.

양의 정수 $N$이 주어질 때, $N$ 이하인 합성소수 중 가장 큰 값을 구하라.

첫 줄에 테스트 케이스 수 $T$가 주어진다. $(1 \le T \le 10^5)$

다음 $T$개 줄에는 각각 정수 $N$이 하나씩 주어진다. $(1 \le N \le 10^7)$

각 테스트 케이스마다 $N$ 이하인 합성소수 중 가장 큰 값을 한 줄에 하나씩 출력한다. 그런 수가 없으면 $-1$을 출력한다.

출력값은 입력 순서와 같은 순서로 출력한다.