Problem 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 nth element.

Input

The first line contains a positive integer T(1≤T≤5), denoting the number of test cases. 
For each test case: 
A single line contains a positive integer n(1≤n≤107).

Output

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

Sample Input

2 
1 
2

Sample Output

1 
2

题目大意：

给定Kolakoski序列a，求第n位是1还是2 
Kolakoski序列是仅仅由1和2组成的一个无限的序列，它的前几项为1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1,2,1,1,2,1,2,2,1,1,……通过将相同的数字分为一组，原序列a的第i位表示第i组有几个元素，a是Kolakoski序列，b表示第i组的元素个数，根据下图来看 

b[2]=a[2]=2，所以第二组有两个元素，第二组只有一个2，所以a[3]=2，所以b[3]=a[3]=2，所以第三组是两个元素，因为上一组是2，所以第三组是1，所以a[4]，a[5]都是1，也可以发现第奇数组的元素是1，第偶数组的元素是2，所以根据这个规律直接打表

c++

#include<cstdio>
using namespace std;
int a[10000005];
int main()
{
    a[1]=1;a[2]=a[3]=2;
    int x=3;bool falg=true;
    for(int i=3;;i++)
    {
        if(a[i]==2)
        {
            if(falg)
            {
                a[++x]=1;a[++x]=1;falg=!falg;
            }
            else
            {
                a[++x]=2;a[++x]=2;falg=!falg;
            }
        }
        else
        {
            if(falg)
            {
                a[++x]=1;falg=!falg;
            }
            else
            {
                a[++x]=2;falg=!falg;
            }
        }
        if(x>10000004)
         break;
    }
    int T;
    scanf("%d",&T);
    while(T--){
        int b;
        scanf("%d",&b);
        printf("%d\n",a[b]);
    }
    return 0;
}