구골 문자열

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

• 전환: 모든 0은 1이 되고, 모든 1은 0이 된다. 예를 들어, "100"은 "011"이 된다.

• 뒤집기: 문자열을 뒤집는다. 예를 들어, "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}$)).

구골 = $10^{100}$일 때, $S_{googol}$의 K번째 문자를 알아내야 한다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. 1 ≤ T ≤ 100.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ K ≤ $10^{5}$.

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ K ≤ $10^{18}$.

입력의 첫째 줄에는 테스트 케이스의 수 T가 주어진다. 다음 T개의 각 줄에는 수 K가 주어진다.

각 테스트 케이스마다 "Case #x: y"을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 $S_{googol}$의 K번째 문자이다.