만드는 중입니다

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

구골 문자열 (Small)

면접 대비

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

요약
중간 0과 뒤집고 바꾼 꼬리를 덧붙여 재귀 0/1 문자열을 만든 뒤 각 테스트 케이스의 K번째 문자를 구합니다.
난이도

쉬움10점 중 3점

유형
재귀, 시뮬레이션
정답자
아직 제출이 없습니다

문제

"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은 1010010^{100}이다. SgoogolS_{googol}의 KK번째 문자를 구하라. 문자의 위치는 1번부터 센다.

입력

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

출력

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

제한

  • 1≤T≤1001 \le T \le 100
  • 1≤K≤1051 \le K \le 10^5

예제4

  1. 예제 1

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

  2. 예제 2

    입력
    1
1
    예상 출력
    Case #1: 0

  3. 예제 3

    입력
    31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
    예상 출력
    Case #1: 0
Case #2: 0
Case #3: 1
Case #4: 0
Case #5: 0
Case #6: 1
Case #7: 1
Case #8: 0
Case #9: 0
Case #10: 0
Case #11: 1
Case #12: 1
Case #13: 0
Case #14: 1
Case #15: 1
Case #16: 0
Case #17: 0
Case #18: 0
Case #19: 1
Case #20: 0
Case #21: 0
Case #22: 1
Case #23: 1
Case #24: 1
Case #25: 0
Case #26: 0
Case #27: 1
Case #28: 1
Case #29: 0
Case #30: 1
Case #31: 1

  4. 예제 4

    입력
    12
1
2
3
4
5
6
7
8
9
10
11
12
    예상 출력
    Case #1: 0
Case #2: 0
Case #3: 1
Case #4: 0
Case #5: 0
Case #6: 1
Case #7: 1
Case #8: 0
Case #9: 0
Case #10: 0
Case #11: 1
Case #12: 1