연속한 소수

Ada는 친구 John을 위해 비밀 선물을 샀다. 선물을 열기 위해 Ada는 John이 비밀 코드를 풀기를 바란다. 그녀는 John이 쉽게 풀 수 있도록 힌트를 주기로 한다. 그녀는 비밀 코드가 연속한 두 소수의 곱으로 만들 수 있는 수이며, $\mathbf{Z}$보다 작거나 같은 수 중 가장 큰 수라고 알려 준다. $\mathbf{Z}$의 값이 주어질 때, John이 비밀 코드를 알아내도록 도와주자.

형식적으로, 소수들의 순서 $2, 3, 5, 7, 11,$ ...를 $p_1, p_2, p_3, p_4, p_5,$ ... 등으로 나타내자. $R_i$를 연속한 두 소수 $p_i$와 $p_{i+1}$의 곱이라고 하자. 비밀 코드는 $R_j \le \mathbf{Z}$를 만족하는 가장 큰 $R_j$이다.

제한

시간 제한: 15초. 메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$.

테스트 세트 1

$6 \le \mathbf{Z} \le 2021$.

테스트 세트 2

$6 \le \mathbf{Z} \le 10^9$.

테스트 세트 3

$6 \le \mathbf{Z} \le 10^{18}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 줄이 주어진다. 각 줄에는 Ada가 힌트의 일부로 제공한 수를 나타내는 정수 $\mathbf{Z}$ 하나가 주어진다.

각 테스트 케이스마다 Case #$x$: $y$를 포함하는 한 줄을 출력한다. 여기서 $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 연속한 두 소수의 곱인 수 중 $\mathbf{Z}$보다 작거나 같은 가장 큰 수인 비밀 코드이다.

예제 케이스 #1에서 비밀 코드는 $2021$이다. 이는 연속한 소수 $43$와 $47$의 곱과 정확히 같기 때문이다.

예제 케이스 #2에서 비밀 코드는 $1763$이다. $41$와 $43$의 곱은 $1763$로 $2020$보다 작지만, $43$와 $47$의 곱은 주어진 값 $2020$를 초과하기 때문이다.