Problem 1121. -- 聪明的张老师

1121: 聪明的张老师

Time Limit: 3 Sec  Memory Limit: 512 MB
Submit: 71  Solved: 25
[Submit][Status][Web Board]

Description

新格尔公司的程序员王大锤,在学习数学的时候看到这样一道题。在犹太罗马战争期间,约瑟夫和其他四十个犹太反抗者被困在了罗马人包围的洞穴中。这些反抗者宁愿自杀也不愿被活捉,于是决定围成一个圈,并沿着圈每隔一个人杀死一个人,直到剩下一个为止。而约瑟夫不希望无谓的自杀,于是他迅速计算出了在圆圈中应该位置。王大锤不会做,只能跑去求助聪明的张老师,张老师觉得在41个人中找到最后安全的位置太简单了,于是出了下面这道题。从记号为1到n的圆圈的n个人开始,每隔一个删去一个人,直到只有一个人幸存下来,输出他的记号。例如n=10,消去的顺序是2,4,6,8,10,3,7,1,9。于是5幸存了下来。

Input

题目包含多组数据。
第一行一个整数T,表示有T组测试数据。(1T ≤ 1000)
对于每组数据有1行,一个正整数N,表示人数。(1N10200)

Output

对于每组数据,第一行输出Case #x: (x编号从1开始)
第二行输出一个数字,幸存者编号。

Sample Input

5
1
2
3
4
41

Sample Output

Case #1:
1
Case #2:
1
Case #3:
3
Case #4:
1
Case #5:
19

HINT

Source

[Submit][Status]