【fjwc2014】猜数字

2014年2月16日1,5400

Description

K国在胖哥的英明统治下,近来迷上了一款非常脑残的游戏,叫做猜数字,这个游戏是一个二人游戏,胖哥认为它非常有利于促进两个人之间的感情,假设玩家A和玩家B进行这个游戏,首先他们会确定一个正整数n,然后A从1-n中选定一个整数,注意一旦选定之后只有游戏结束都不能修改这个数字,假设这个数字是x,然后游戏开始,每次B都可以在1-n中选择一个整数,假设这个数字是y,然后A会告诉他gcd(x,y)的值,即x和y的最大公约数,B可以利用之前A回答的结果决定每一轮中他所选择的数字,如果在某一时刻,B可以用A回答的结果推理出A选择的数字,则游戏结束,假设n=6,如果A选定了数字2,然后第一轮B询问了数字6,A回答2,这时B可以推断出A手中的数字只能是2或者4,然后B询问数字2就可以知道A手中的数字了(这只是一种可能的游戏进行方式,可能并非最优策略),作为K国的国王,胖哥已经疯狂的迷恋上了这个游戏,他想要知道,对于一个确定的正整数n,在最坏的情况下游戏会进行几轮,即无论A选择了什么数字,B都可以保证有一个策略使得游戏在这么多轮之内结束,可以游戏双方都遵循最优策略进行,同时你可以认为K国的国民都十分诚实,他们一旦选定了数字之后就永远不会改变

 

Input

首先输入一个数Q,表示有Q(Q ≤ 10)组样例

每组样例首先输入一个整数n (2 ≤ n ≤ 10000),表示在这组样例中游戏前确定的正整数n

 

Output

对于每组样例,首先输出样例编号,之后输出在最优策略下,最坏的情况需要询问几次,具体格式见sample output

 

Sample Input

4

2

3

5

6

 

 

Sample Output

Case 1: 1

Case 2: 2

Case 3: 3

Case 4: 2

 

 

 

数据范围:

 

 

样例                     n

1                          ≤ 10

2                          ≤ 20

3                          ≤ 50

4                          ≤ 100

5                          ≤ 200

6                          ≤ 1000

7                          ≤ 10000

8                          ≤ 10000

9                          ≤ 10000

10                         ≤ 10000

贪心策略

若想知道对方手中的数字。需要确定是否存在《=n的每一个质数

如n=10,要分别确定2,3,5,7

首先的想法是把小的质数放在一起问

但是发现大质数每个依然要问一次

所以应该把大质数后小质数一起问

由于n《=10000

所以我们可以.。。打表