Problem Description
Given an integer n, it generates a tree by the following operation.
Initially, there is a node weights n.
If n is not a prime number, the nodes gets a left son and a right son, the left son weights x, where x is a factor of n and x is larger than 1 and smaller than n chosen randomly, and the right son weights n/x. We call this step split.
For each leaf of tree, we do the split operation, until all of the leaves weight a prime number.
For example, suppose n to be 12, and the picture below shows a tree generated.
Now we want to know the expectated height of the tree.
Input
There are multiply test cases.
The first line contains an integer T(T<=50000), which denotes the number of test cases.
For each test case, there is an integer n(2<=n<=10^11), denotes the weight of the root.
The test cases are generated almost randomly.
Output
For each test case, output “Case #k: ”first, k is the case number, from 1 to T , and then output the expectated height. The answer should be rounded after the sixth decimal place.
Sample Input
3
2
4
36
Sample Output
Case #1: 1.000000
Case #2: 2.000000
Case #3: 3.571429
