Easy Sequence 1

Limits 1s, 512 MB

Let’s define an easy sequence FF. Where:

F(1)=1F(1)=1

F(2X)=F(X)2+1F(2X) = F(X)^2 + 1

F(2X+1)=F(X)×F(X+1)+2F(2X+1) = F(X) \times F(X+1) + 2

Here XX is a positive integer. The first few elements of the sequence are 1, 2, 4, 5, 10, 17, 22, 26, 52, 101.

Now given a value of F(X) F(X) , can you compute XX?

Input

The first line of the input is a positive integer TT (T100T ≤ 100), the number of test cases. Then TT lines follow.

In each line there will be a value of F(X) F(X) (1F(X)1091 ≤ F(X) ≤ 10^9). It is guaranteed that for every F(X) F(X) in the input, there exists a valid XX.

Output

For each case print a line in Case I: X\texttt{Case I: X} format where I\texttt{I} is the test case number and X\texttt{X} is the corresponding value for the given F(X) F(X) in the input.

Sample

InputOutput
10
1
2
4
5
10
17
22
26
52
101
Case 1: 1
Case 2: 2
Case 3: 3
Case 4: 4
Case 5: 5
Case 6: 6
Case 7: 7
Case 8: 8
Case 9: 9
Case 10: 10