연속한 두 소수의 곱

Ada는 친구 John을 위해 비밀 선물을 하나 샀다. 선물을 열려면 John이 비밀 코드를 풀어야 한다. Ada는 John이 쉽게 풀 수 있도록 힌트를 하나 주기로 한다. Ada는 비밀 코드가 두 연속한 소수의 곱으로 만들 수 있는 수 가운데 $Z$ 이하인 가장 큰 수라고 알려 준다. $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 Z$를 만족하는 가장 큰 $R\_j$이다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 다음 $T$개의 줄이 이어진다.

각 줄에는 정수 $Z$가 하나씩 주어지며, 이는 Ada가 힌트로 알려 준 수이다.

각 테스트 케이스마다 한 줄에 Case #x: y를 출력한다. 여기서 $x$는 테스트 케이스 번호(1부터 시작)이고, $y$는 비밀 코드, 즉 $Z$ 이하이면서 두 연속한 소수의 곱인 가장 큰 수이다.

• $1 \le T \le 100$.

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

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