Prime Tree

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.

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.

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.

3
2
4
36

Case #1: 1.000000
Case #2: 2.000000
Case #3: 3.571429

UESTC

2014 Multi-University Training Contest 7