Dilu have learned a new thingabout integers, which is - any positive integer greater than 1 can be divided byat least one prime number less than or equal to that number. So, he is nowplaying with this property. He selects a number N. And he calls this D.

In each turn he randomly chooses aprime number less than or equal to D.If D is divisible by the prime numberthen he divides D by the primenumber to obtain new D. Otherwise hekeeps the old D. He repeats thisprocedure until D becomes 1. What isthe expected number of moves required for Nto become 1.

[We say that an integer is said tobe prime if its divisible by exactly two different integers. So, 1 is not aprime, 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 ofthe next T lines will contain oneinteger N (1 <= N <= 1000000).

Output

For each test case output a single line giving the casenumber followed by the expected number of turn required. Errors up to 1e-6 willbe accepted.

SampleInput Outputfor Sample Input

Problemsetter: Md. Arifuzzaman Arif

Special Thanks: Sohel Hafiz

题意：给你一个整数N，每次都可以在不超过N的素数中随机选择一个P，如果P是N的约数，则把N变成N/P，否则N不变，问平均情况下要多少次随机选择，才能把N变成1

思路：设f(i)表示当前的数为i时接下来需要选择的次数，这样我们就能得到一个方程，例如：f(6)=1+f(6)+1/3+f(3)*1/3+f(2)*1/3

我们设不超过x的素数有p(x)个，其中有g(x)个是x的因子，则f(x) = 1 + f(x)*(1-g(x)/p(x)) + f(x/y)/p(x){y是x的素因子}，移项后整理得f(x)=(f(x/y)+p(x))/g(x){y是x的因子}，因为

x/y

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       typedef long long ll; using namespace std; const int maxn = 1000005; const int maxm = 100000; double f[maxn]; int prime[maxm], cnt, vis[maxn]; void init() { memset(vis, 0, sizeof(vis)); cnt = 0; f[0] = f[1] = 1; for (ll i = 2; i < maxn; i++) if (!vis[i]) { prime[cnt++] = i; for (ll j = i*i; j < maxn; j += i) vis[j] = 1; } } double dp(int x) { if (x == 1) return 0.0; if (vis[x]) return f[x]; vis[x] = 1; double &ans = f[x]; int g = 0, p = 0; ans = 0; for (int i = 0; i < cnt && prime[i] <= x; i++) { p++; if (x % prime[i] == 0) { g++; ans += dp(x / prime[i]); } } ans = (ans + p) / g; return ans; } int main() { init(); memset(vis, 0, sizeof(vis)); int t, n, cas = 1; scanf("%d", &t); while (t--) { scanf("%d", &n); printf("Case %d: %.10f\n", cas++, dp(n)); } return 0; }