P16502 [GKS 2015 #A] Googol String

A "0/1 string" is a string in which every character is either 0 or 1. There are two operations that can be performed on a 0/1 string: - **switch**: Every 0 becomes 1 and every 1 becomes 0. For example, "100" becomes "011". - **reverse**: The string is reversed. For example, "100" becomes "001". Consider this infinite sequence of 0/1 strings: $S_0 = ``"$ $S_1 = ``0"$ $S_2 = ``001"$ $S_3 = ``0010011"$ $S_4 = ``001001100011011"$ ... $S_N = S_{N-1} + ``0" + \textbf{switch}(\textbf{reverse}(S_{N-1}))$. You need to figure out the Kth character of $S_{\text{googol}}$, where googol = $10^{100}$.

The first line of the input gives the number of test cases, $T$. Each of the next $T$ lines contains a number $K$.

For each test case, output one line containing "Case #x: $y$", where $x$ is the test case number (starting from $1$) and $y$ is the Kth character of $S_{\text{googol}}$.

### Limits $1 \le T \le 100$. **Small dataset (Test Set 1 - Visible)** $1 \le K \le 10^5$. **Large dataset (Test Set 2 - Hidden)** $1 \le K \le 10^{18}$.