[UVa 11762]得到1

Grade Open Time Friday, 19 September 2014, 10:07 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:07 am
Allow late Yes Close Time Friday, 26 September 2014, 10:07 am
Input file RaceTo1.in Output file RaceTo1.out

【题目描述】

给出一个整数N,每次可以在不超过N的素数中随机选取一个P,如果P是N的约数,则把N变成N/P,否则N不变。问平均情况下需要多少次随机选择,才能把N变成1?比如N=3时,答案为2,N=13时,答案为6.

【输入格式】

输入第一行为数据组数T(T≤1 000),以下T行每行为一个整数N(1≤N≤1 000 000).

【输出格式】

对于每组数据,输出平均情况需要的操作次数。

Sample


  Input                           

 3

 1

 3

 13

  Output

 Case1: 0.0000000000

 Case2: 2.0000000000

 Case3: 6.0000000000


【来源】

Race To 1,UVa 11762.


Problemsetter: Md. Arifuzzaman Arif

Special Thanks: Sohel Hafiz