Practice on Toph

Let’s define an easy sequence F. Where

F(1) = 1
F(2X) = F(X)² + 1
F(2X+1) = F(X) * F(X+1) + 2

Here X is a positive integer. So, the first few elements of the sequence is 1, 2, 4, 5, 10, 17, 22, 26, 52, 101 and so on.

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

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) <= 1000000000 or 10⁹ ). It is guaranteed that for every F(X) in the input, there exists a valid X.

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.