小汤的朋友杰克刚刚向他展示了一个很棒的魔术。魔术开始时，地上有一个盒子，里面装有一定数量的球。杰克随后反复执行以下操作：
- 在地上放一个新的空盒子
- 从其他每个盒子中各取出一个球放入这个新的空盒子中
- 移除所有现在变为空的盒子
- 将盒子按球的数量进行非递减排序
小汤注意到，这个操作有可能使盒子和球的状态保持不变！例如：
- 假设魔术开始时，这一个盒子里装有 3 个球。
- 在第一次操作中，杰克增加了一个新的空盒子，从现有的盒子里取出 1 个球放入其中，并对盒子进行排序。因此，操作后地上会有 2 个盒子，一个装有 1 个球，另一个装有 2 个球。
- 在第二次操作中，杰克增加了一个新的空盒子，并从现有的 2 个盒子里各取出 1 个球放入其中；这产生了一个空盒子，杰克将其移除，然后对盒子进行排序。此时地上有 2 个盒子，一个装有 1 个球，另一个装有 2 个球。这正是第二次操作前的状态！
小汤进一步思考了这个魔术，意识到对于某些球的数量，该操作无法使状态保持不变。例如，如果开始时有 2 个球，那么在一次操作后，会有两个各装有 1 个球的盒子；在两次操作后，会有一个装有 2 个球的盒子，以此类推，在这两种状态之间无限循环。
小汤环顾房间，发现有无数个空盒子，但只有 $N$ 个球。他最多能使用多少个球来表演这个魔术，使得一次操作后状态保持不变？
输入格式
第一行输入包含测试用例的数量 $T$。接下来有 $T$ 行。 每行包含一个整数 $N$，即小汤能找到的球的数量。
输出格式
对于每个测试用例，输出一行 “Case #x: y”，其中 x 是测试用例编号（从 1 开始），y 是小汤能用于表演魔术（如上所述，使得状态保持不变）的最大球数。
数据范围
- $1 \le T \le 100$
- $1 \le N \le 10^{18}$
样例
样例输入 1
3 1 2 3
样例输出 1
Case #1: 1 Case #2: 1 Case #3: 3
说明
该魔术可以用 1 个球或 3 个球来表演，但不能用 2 个球。因此，对于 Case #2，小汤在 2 个球中最多只能使用 1 个。