구골 문자열 (라지)

"0/1 문자열"은 모든 문자가 0 또는 1인 문자열이다. 0/1 문자열에는 두 가지 연산을 적용할 수 있다.

• switch: 모든 0을 1로, 모든 1을 0으로 바꾼다. 예를 들어 "100"은 "011"이 된다.
• reverse: 문자열을 뒤집는다. 예를 들어 "100"은 "001"이 된다.

0/1 문자열로 이루어진 다음 무한 수열을 생각하자.

• $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}$))

$\mathrm{googol} = 10^{100}$이라고 할 때, $S_{\mathrm{googol}}$의 $K$번째 문자를 구하라. 문자의 위치는 1부터 센다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어지는 $T$개의 줄에 정수 $K$가 한 줄에 하나씩 주어진다.

각 테스트 케이스마다 "Case #x: y" 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 $S_{\mathrm{googol}}$의 $K$번째 문자이다.

• $1 \le T \le 100$
• $1 \le K \le 10^{18}$