1313번 - 합성소수

문제

1313ドル$은 $ 13 \times 101$로 소인수분해되므로 합성수이지만, 1313ドル$의 연속되는 진부분수 13ドル,ドル 31ドル,ドル 13ドル,ドル 131ドル,ドル 313ドル$은 모두 소수이다.

이 문제에서, 연속되는 진부분수란 세 자리 이상의 양의 정수 $N$에 대하여 $N$의 십진수 표현에서 연속된 2개 이상의 숫자를 선택해 순서를 유지해서 만들 수 있는 수 중 $N$을 제외한 음이 아닌 정수라고 정의한다.

1313ドル$과 같이, 양의 정수 $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 $ 이하인 합성소수 중 가장 큰 수를 출력한다. 만약 $ N $ 이하인 합성소수가 존재하지 않는다면 그 대신 $-1$을 출력한다.

예제 출력과 같이 각 테스트케이스의 출력값은 입력 순서대로 한 줄에 하나씩 출력되어야 한다.

제한

힌트