Race to 1

Dilu have learned a new thing about integers, which is - any positive integer greater than 1 can be divided by at least one prime number less than or equal to that number. So, he is now playing with this property. He selects a number N. And he calls this D. In each turn he randomly chooses a prime number less than or equal to D. If D is divisible by the prime number then he divides D by the prime number to obtain new D. Otherwise he keeps the old D. He repeats this procedure until D becomes 1. What is the expected number of moves required for N to become 1. [We say that an integer is said to be prime if its divisible by exactly two different integers. So, 1 is not a prime, by definition. List of first few primes are 2, 3, 5, 7, 11, ...] Input Input will start with an integer T (T ≤ 1000), which indicates the number of test cases. Each of the next T lines will contain one integer N (1 ≤ N ≤ 1000000). Output For each test case output a single line giving the case number followed by the expected number of turn required. Errors up to 1e-6 will be accepted. Sample Input 3 1 3 13 Sample Output Case 1: 0.0000000000 Case 2: 2.0000000000 Case 3: 6.0000000000