Limits
1s, 512 MB
Let’s define an easy sequence F. Where:
F(2X)=F(X)2+1 F(2X+1)=F(X)×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
Input | Output |
---|
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
|

Factors
| CPU | Memory | Source |
---|
Bash 5.0 | 1× | 1× | 1× |
Brainf*ck | 1× | 1× | 1× |
C# Mono 6.0 | 1× | 1× | 1× |
C++11 GCC 7.4 | 1× | 1× | 1× |
C++14 GCC 8.3 | 1× | 1× | 1× |
C++17 GCC 9.2 | 1× | 1× | 1× |
C++20 GCC 12.1 | 1× | 1× | 1× |
C11 GCC 12.1 | 1× | 1× | 1× |
C11 GCC 9.2 | 1× | 1× | 1× |
Common Lisp SBCL 2.0 | 1× | 1× | 1× |
D8 11.8 | 1× | 1× | 1× |
Erlang 22.3 | 1× | 1× | 1× |
Free Pascal 3.0 | 1× | 1× | 1× |
Go 1.18 | 1× | 1× | 1× |
Grep 3.7 | 1× | 1× | 1× |
Haskell 8.6 | 1× | 1× | 1× |
Java 1.8 | 1× | 1× | 1× |
Kotlin 1.1 | 1× | 1× | 1× |
Lua 5.4 | 1× | 1× | 1× |
Node.js 10.16 | 1× | 1× | 1× |
Perl 5.30 | 1× | 1× | 1× |
PHP 7.2 | 1× | 1× | 1× |
PyPy 7.1 (2.7) | 1× | 1× | 1× |
PyPy 7.1 (3.6) | 1× | 1× | 1× |
Python 2.7 | 1× | 1× | 1× |
Python 3.11 | 1× | 1× | 1× |
Ruby 2.7 | 1× | 1× | 1× |
Ruby 3.2 | 1× | 1× | 1× |
Rust 1.57 | 1× | 1× | 1× |
Swift 5.3 | 1× | 1× | 1× |
Whitespace | 1× | 1× | 1× |
Python 3.7 | 1× | 1× | 1× |