Problem D
Non-Decreasing Prime Sequence

Input: Standard Input

Output: Standard Output

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
2	2
2 5 13	130 (2 X 5 X 13)
2 3 97	582 (2 X 3 X 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 Output for Sample Input

3 2 10 1 2 10 5 2 10 9

Case 1: 2 Case 2: 2 2 Case 3: 2 2 2

Problem setter: Arifuzzaman Arif

Special Thanks: Manzurur Rahman Khan