Under construction

Still being built. Things may change

Googol String (Large)

Interview

Time limit5sMemory limit512 MB

Summary
Answer the Kth character of a recursively defined binary string for each query with K up to 10^18.
Level

Medium5 of 10

Topics
Recursion, Bit manipulation
Solved
No attempts yet

Problem

A "0/1 string" is a string in which every character is either 0 or 1. Two operations apply 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 this infinite sequence of 0/1 strings.

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

Let googol=10100\mathrm{googol} = 10^{100}. Find the KKth character of SgoogolS_{\mathrm{googol}}. Positions are counted from 1.

Input

The first line contains the number of test cases TT. Each of the next TT lines contains one integer KK.

Output

For each test case, print one line in the form "Case #x: y", where xx is the test case number starting from 1 and yy is the KKth character of SgoogolS_{\mathrm{googol}}.

Constraints

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

Examples1

  1. Example 1

    Input
    4
1
2
3
10
    Expected output
    Case #1: 0
Case #2: 0
Case #3: 1
Case #4: 0