Description

Salted fish Albert_s is a Sagittarius who will never grow up, especially in front of someone he like. Here's his self-portrait:

One day, he find a wonderful sequence: $1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1$……. This sequence consists of $1$ and $2$, and its first term equals $1$. Besides, if you see adjacent and equal terms as one group, you will get $1,22,11,2,1,22,1,22,11,2,11,22,1$……. Count number of terms in every group, you will get the sequence itself. Now, the sequence can be uniquely determined.

Forsaken and Wanderer attracted by this sequence, and they want to know what's the $n_{th}$​ element. Because of something sadness, Albert_s is unable to think now. Would you like to help him?

Format

Input

The first line contains a positive integer T($1 \leq T \leq 10$), denoting the number of test cases.
For each test case:
A single line contains a positive integer n(​$1 \leq n \leq 10^7$​), denoting the index of the element in the sequence.

Output

For each test case:
A single line contains a nonnegative integer, denoting the answer.

Samples

2
1
2

1
2