# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Easy Sequence 1

By ridowan007 · Limits 1s, 512 MB

Let’s define an easy sequence F. Where

$F(1) = 1$

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

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

Here X 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)$, can you compute X?

## Input

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

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

## Output

For each case print a line in “Case I: X” format where I is the test case number and X is the corresponding value for the given $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

### Statistics

86% Solution Ratio

mizan_rEarliest, Jun '16

drifter.pustFastest, 0.0s

tamzid_secLightest, 0 B

WhiteCiferShortest, 178B