A prime number is a natural number which has exactly two distinct natural number divisors. First few prime numbers are: 2, 3, 5, 7, 11, 13, ... and so on. A non decreasing prime sequence (NDPS) is a sequence of prime numbers where i-th element is not less than (i − 1)-th element for all i > 1. The weight of a NDPS is the product of all numbers of the sequence. Here are some examples of NDPSs with their corresponding weights. NDPS Weight 22 2 5 13 130 (2 × 5 × 13) 2 3 97 582 (2 × 3 × 97) An NDPS a is smaller than another NDPS b, if number of elements in a is smaller than the number of elements in b. If a and b has same number of elements then lexicographically smaller sequence is the smaller NDPS. For the list given above, {2} is the smallest sequence because it has only one elements. {2 5 13} and {2 3 97} both have 3 elements, so {2 3 97} is second smallest because it is lexicographically smaller than {2 5 13}. For a given range (A, B), where A ≤ B, you have to find the K-th smallest NDPS between all the NDPSs having weights in between A and B (inclusive). Input Input will start with an integer T (T ≤ 5000), the number of test cases. Each of the next T line will contain three integers A, B and K (2 ≤ A ≤ B ≤ 1000000). K is a positive integer and you can safely assume that at least K NDPSs exists in the given range. Output For each case, you have to output one line, case number followed by the K-th smallest NDPS between all the NDPSs having weights between A and B (inclusive). See sample output for exact format. Sample Input 3 2 10 1 2 10 5 2 10 9 Sample Output Case 1: 2 Case 2: 2 2 Case 3: 2 2 2