Migrated from Lutece 308 Boring 11.11

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

On the famous Singles' Day (Guanggun Jie in Chinese) in 2011, our fellow TC is still a poor Guanggun without any girl beside :-( . He was especially depressed when seeing many other boys find their girls, so he began to hate anything that looks like Guanggun, including the number 1. As a result, he began to count the 1s in every number in its binary notation, if a number has a lot of 1s, he hated it a lot. TC wants to sort all the numbers by the 1s they contain.

Now our question is: Given a number $N$, can you find another number $M$ bigger than $N$, making $M$ and $N$ have exactly the same number of 1s, when written in binary notation? You are required to make your number $M$ as small as possible.

Input

The first line of the input contains only one integer $T$.

Then $T$ lines follow, every line contains only one integer $N$ ($1\leq N\leq 10^9$).

Output

For each test case, output one line. First ,output Case #C: , where $C$ is the number of test case, from $1$ to $T$.

Then , output the smallest $M$ you find for each $N$.

Samples

2
2
10

Case #1: 4
Case #2: 12

Note

In case $2$ of sample, 1010 is the binary form of decimal number $10$, and 1100 is the binary notation of decimal number $12$. Apparently, $12$ is smallest one which share the same number with $10$ and it is bigger than $10$.

Resources

GreenWall & ahxgw