小雷的一树枣

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

小雷为了证明自己雄风不减当年,一大清早背了一筐竹子去给队友打枣去。经过千辛万苦,跋山涉水,踏破铁鞋,行万里路,after long long long long long long long long long .........(此处省略好多好多好多好多个long)hours,小雷终于赶在天黑前找到了北门的一颗枣树。树上有n个枣,门卫大大害怕小雷把枣树打光,限制小雷每竿只能打素数个枣。小雷当即拿出一摞草稿纸,想要计划出一个打枣方案,打走尽量多的枣。你能用程序帮小雷快速规划出打枣大计么。
PS:
素数的定义:除了1以外,能且只能被1和它本身整除的正整数,叫做素数。

Input

多组输入,第一行一个整数T(T < = 100)表示组数。
之后T行每行一个整数(0 <= n < 10^9)。

Output

 对于每组输入,先输出Case z: 再输出一个整数表示能够打下的最多枣数。每组输出占一行。

Sample Input

3
1
2
3

Sample Output

Case 1: 0
Case 2: 2
Case 3: 3

Hint

 

Source

2015年第五届ACM趣味编程循环赛(第一场) by LeiQ