Rimi learned a new thing about integers, which is - any positive integer greater than 1 can be divided by its divisors. 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 divisor of D (1 to D). Then he divides D by the number to obtain new D. He repeats this procedure until D becomes 1. What is the expected number of moves required for N to become 1.

Input

Input starts with an integer T (≤ 10000), denoting the number of test cases.

Each case begins with an integer N (1 ≤ N ≤ 105).

Output

For each case of input you have to print the case number and the expected value. Errors less than 10-6 will be ignored.

Sample Input

3

1

2

50

Sample Output

Case 1: 0

Case 2: 2.00

Case 3: 3.0333333333

题意：

现在有一个数n，每次n可以变成自己因子，问你使得n变成1的步数期望是多少

思路：

和前面两个bzoj3036一样，但是你会发现多了一个环的走法，就比如

10可以由1,2,5,10算来贡献，就出现了自环，那么方程就可以列出，然后移项一下就可以得到答案了，再枚举一下每个数的因子即可

E(10) = (E(10) + 1 + E(5) + 1 + E(2) + 1 +  E(1) + 1) / 4

移项计算就可以了

代码：

vector<int>v; double f[100050]; int main() { int t; int cas = 1; cin >> t; while(t--){ cin >> n;v.clear(); for(int i = 1;i * i <= n;i++){ if(n % i == 0){ if(n / i == i) v.pb(i); else v.pb(i),v.pb(n / i); } } MS0(f); sort(all(v)); f[1] = 0; for(int i = 1;i < v.size();i++){ int x = v[i],cnt = 0; for(auto d:v){ if(d >= x) break; if(x % d == 0){ cnt++; f[x] += 1 + f[d]; } } if(cnt){ f[x] += 1; f[x] /= (1.0 * (cnt)); }else f[x] = 2; } printf("Case %d: %.6f\n",cas++,f[n]); } return 0; }