23005번 - Consecutive Primes 서브태스크다국어

Ada has bought a secret present for her friend John. In order to open the present, Ada wants John to crack a secret code. She decides to give him a hint to make things simple for him. She tells him that the secret code is a number that can be formed by taking the product of two consecutive prime numbers, such that it is the largest number that is smaller than or equal to $Z$. Given the value of $Z$, help John to determine the secret code.

Formally, let the order of prime numbers 2, 3, 5, 7, 11, ... be denoted by $p_1$, $p_2$, $p_3$, $p_4$, $p_5$, ... and so on. Consider $R_i$ to be the product of two consecutive primes $p_i$ and $p_{i+1}$. The secret code is the largest $R_j$ such that $R_j \le Z$.

The first line of the input gives the number of test cases, $T$. $T$ lines follow.

Each line contains a single integer $Z$, representing the number provided by Ada as part of the hint.

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is the secret code - the largest number less than or equal to $Z$ that is the product of two consecutive prime numbers.

• $1 \le T\le 100$.

• $6 \le Z \le 2021$.

• $6 \le Z \le 10^9$.

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

For Sample Case #1, the secret code is 2021 because it is exactly the product of consecutive primes 43 and 47.

For Sample Case #2, the secret code is 1763 because the product of 41 and 43 is 1763 which is smaller than 2020, but the product of 43 and 47 exceeds the given value of 2020.