Kolakoski

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 524288/524288 K (Java/Others)

Description

This is Kolakosiki 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. Please tell HazelFan its $n$th element.

Input

The first line contains a positive integer $T(1\leq T\leq5)$, denoting the number of test cases.
For each test case:
A single line contains a positive integer $n(1\leq n\leq10^7)$.

Output

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

Sample Input

2 1 2

Sample Output

1 2

Hint

liuyiding

Source

2017 Multi-University Training Contest - Te

提交代码