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

所以我们可以.。。打表