E. Binary Mirror Maze
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Welcome to the Binary Mirror Maze!

We start with an empty bit string: $$$s_0$$$ = ""

Then, for each integer $$$i \geq 0$$$, construct the next string as follows: $$$s_{i+1} = s_i +$$$ "$$$0$$$" + mirror($$$s_i$$$) Here, mirror(s) means that we first reverse the string s, and then invert each bit (swap every "$$$0$$$" with "$$$1$$$" and every "$$$1$$$" with "$$$0$$$").

For example:

  • For $$$s_0$$$ = "", we have: $$$s_1$$$ = "" + "0" + mirror("") = "0"

  • For $$$s_1$$$ = "0", since mirror("0") = "1", we get: $$$s_2$$$ = "0" + "0" + "1" = "001"

  • For $$$s_2$$$ = "001": mirror("001") → reverse("001") = "100", then invert to obtain "011" Thus, $$$s_3$$$ = "001" + "0" + "011" = "0010011"
It can be shown that every string $$$s_i$$$ is a prefix of an infinitely long bit string t.

Your task is: Given an integer k, find the k-th character (1-indexed) of the string t.

Input

In the first line you will be given an integer $$$T (1 \le T \le 10^5)$$$ the number of test cases. Each of the next $$$T$$$ following lines you will be given a single integer $$$k(1 \le k \le 10^{18})$$$.

Output

For each integer $$$k$$$ output the $$$k-th$$$ caracter in the infinitely long string $$$t$$$.

Example
Input
5
2
9
6
4
5
Output
0
0
1
0
0