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变成1的期望步数。

简单期望dp，不难想到，我们递推期望的时候，和当前数字的因子个数有关。

我们令 dp[i] 为数字i变为1的期望步数，然后对因子递推即可。

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
vector<int> v[N];
int T,n,ts;
double dp[N];
void get(){
    for(int i=1;i<=1e5;i++){
        for(int j=i;j<=1e5;j+=i)    v[j].push_back(i);
    }
}
int main(){
    cin>>T; get();
    for(int i=2;i<=1e5;i++){
        for(int j=0;j<v[i].size();j++){
            int p=i/v[i][j];    dp[i]+=dp[p]/v[i].size();   
        }
        dp[i]++;
        dp[i]=dp[i]*v[i].size()/(v[i].size()-1);
    }
    while(T--){
        cin>>n; printf("Case %d: %.8lf\n",++ts,dp[n]);
    }
    return 0;
}