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 consecutive prime numbers, such that it is the largest number that is smaller than or equal to . Given the value of , help John to determine the secret code.
Formally, let the order of prime numbers be denoted by and so on. Consider to be the product of consecutive primes and . The secret code is the largest such that .
输入格式
The first line of the input gives the number of test cases, . lines follow.
Each line contains a single integer , representing the number provided by Ada as part of the hint.
输出格式
For each test case, output line containing Case #x: followed by , where is the test case number (starting from ) and is the secret code - the largest number less than or equal to that is the product of consecutive prime numbers.
样例
样例输入 1
2
2021
2020
样例输出 1
Case #1: 2021
Case #2: 1763
数据范围与提示
For Sample Case #, the secret code is because it is exactly the product of consecutive primes and .
For Sample Case #, the secret code is because the product of and is which is smaller than , but the product of and exceeds the given value of .
