Googol String (Small)

A "0/1 string" is a string in which every character is either 0 or 1. Two operations can be applied to 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 the infinite sequence of 0/1 strings defined below.

• $S_0$ = ""
• $S_1$ = "0"
• $S_2$ = "001"
• $S_3$ = "0010011"
• $S_4$ = "001001100011011"
• ...
• $S_N$ = $S_{N-1}$ + "0" + switch(reverse($S_{N-1}$))

googol is $10^{100}$. Find the $K$th character of $S_{googol}$. Character positions are counted from 1.

The first line contains the number of test cases, $T$. Each of the next $T$ lines contains one integer $K$.

For each test case, print one line in the form "Case #x: y", where x is the test case number starting from 1 and y is the $K$th character of $S_{googol}$.

• $1 \le T \le 100$
• $1 \le K \le 10^5$