Problem Description

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}$.

Input Format

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

Output Format

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}}$.

4
1
2
3
10

Case #1: 0
Case #2: 0
Case #3: 1
Case #4: 0

Hint

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}$.