만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

구골 문자열 (라지)

면접 대비

시간 제한5초메모리 제한512 MB

요약
점화식으로 정의된 이진 문자열의 K번째 문자를 각 쿼리마다 구합니다.
난이도

보통10점 중 5점

유형
재귀, 비트 연산
정답자
아직 제출이 없습니다

문제

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

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

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

  • S0S_0 = ""
  • S1S_1 = "0"
  • S2S_2 = "001"
  • S3S_3 = "0010011"
  • S4S_4 = "001001100011011"
  • ...
  • SNS_N = SN−1S_{N-1} + "0" + switch(reverse(SN−1S_{N-1}))

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

입력

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

출력

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

제한

  • 1≤T≤1001 \le T \le 100
  • 1≤K≤10181 \le K \le 10^{18}

예제1

  1. 예제 1

    입력
    4
1
2
3
10
    예상 출력
    Case #1: 0
Case #2: 0
Case #3: 1
Case #4: 0