Googol String (Small)

Problem

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.

Input

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

Output

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

Constraints

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