问题描述

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

输入格式

题目包含多组数据。

第一行一个整数 $T$，表示有 $T$ 组测试数据。（$1 \leq T \leq 1000$）

对于每组数据有 $1$ 行，一个正整数 $N$，表示人数。（$1 \leq N \leq 10^{200}$）

输出格式

对于每组数据，第一行输出 Case #x:（$x$ 编号从 $1$ 开始）。

第二行输出一个数字，幸存者编号。

样例输入

5
1
2
3
4
41

样例输出

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