P16843 [GKS 2021 #B] 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 $2$ 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, \ldots$ be denoted by $p_1, p_2, p_3, p_4, p_5, \ldots$ and so on. Consider $R_i$ to be the product of $2$ 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 $1$ line containing `Case #x:` followed by $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 $2$ consecutive prime numbers.

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$. ### Limits $1 \le T \le 100$. **Test Set $1$** $6 \le Z \le 2021$. **Test Set $2$** $6 \le Z \le 10^9$. **Test Set $3$** $6 \le Z \le 10^{18}$.