Bitstring v2

We call an inifnitely long sequence of 0 and 1 characters a binary sequence if it is the concatenation of the binary forms of 1, 2, 3, 4,.... (For displaying the binary numbers we use as few characters as we possibly can, so 1=1, 2=10, etc.) The beginning of the sequence in decimal form is 123456789101112, which translated to binary is 1101110010111011110001001101010111100. Your task is simple: in this infinitely long binary sequence you are given a couple indices (the starting index of the binary sequence is the 0th index) and you need to print out the value (0 or 1) of those indices in the binary sequence.

Input

The input has two units:

• The first line is a single n positive integer which tells you the number of indices.
• Each of the next n lines contain 1-1 BINARY number which is the representation of each index.

Output

The output is n lines, each of them containing a single 0 or 1 integer. Each line corresponds to the appropriate index in the in the input (so the k-th output line corresponds to the k-th index in the input) and the value is 0 if the value at the k-th index in the binary sequence is 0 and 1 otherwise.

Restrictions

Example