[UVa 11762]得到1

成绩 开启时间 2014年09月19日 星期五 10:07
折扣 0.8 折扣时间 2014年09月26日 星期五 10:07
允许迟交 是 关闭时间 2014年09月26日 星期五 10:07
输入文件 RaceTo1.in 输出文件 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