当前没有测试数据。

题目描述

The relationship between Byteland and Bitland is on thin ice and a war is certained to start. The message of your agent shows that the communication in Bitland is encrypted. They've chosen three different RNGs (Random Number Generators) that can produce a sequence of 0s and 1s. At the start of every day, they'll randomly pick one RNG, pick one random seed and use that RNG to generate a binary sequence of length 2000. This sequence will act as an encryption key. As an officer of Byteland, rather than decrypt the datas, you've decided to solve an easier problem first: for an encyption key generated, figure out which RNG is used to generate it. The following is a sample code of these three RNGs written in the out-dated language, C++ (it's recommend to copy-paste the following code to your favorite editor):

typedef unsigned int u32;
typedef unsigned long long u64;
struct RNG {
virtual void srand(u32 seed)=0;
virtual bool gen()=0;
};
struct RNG0: RNG {
u32 x;
void srand(u32 seed) {x=seed;}
bool gen() {
    x=x*214013u+2531011u;
    return (x>>28)&1;
}
};
struct RNG1: RNG {
int index;
u32 mt[624];
void srand(u32 seed) {
    mt[0]=seed; index=624;
    for(int i=1;i<624;++i)
        mt[i]=1812433253u*(mt[i-1]^(mt[i-1]>>30))+i;
}
void twist() {
    for(int i=0;i<624;++i) {
        u32 y=(mt[i]&0x80000000u)+
              (mt[(i+1)%624]&0x7fffffffu);
        mt[i]=mt[(i+397)%624]^(y>>1);
        if(y&1) mt[i]^=0x9908b0df;
    }
    index=0;
}
bool gen() {
    if(index>=624) twist();
    u32 y=mt[index]; y^=y>>11;
    y^=(y<<7)&2636928640u;
    y^=(y<<15)&4022730752u;
    y^=y>>18; ++index;
    return (y>>16)&1;
}
};
struct RNG2: RNG {
u64 x;
void srand(u32 seed) {x=seed;}
bool gen() {
    x^=x<<13; x^=x>>7; x^=x<<17;
    return (x>>16)&1;
}
};
RNG *rng[3]={new RNG0(),new RNG1(),new RNG2()};

输入格式

The first line contains the number of test cases T. In real data, T=1000.

Each of the following T lines contain a binary string of length 2000 - an encryption key.

输出格式

Output T lines, for the i-th encryption key in the input, output 0 if its generated using RNG0, 1 if generated using RNG1 and 2 if generated using RNG2.

样例

样例输入 1

1
0011101100001010111010001001000000011101001010000110111100111000110010011010000001110011001
0010010101100011001110000010000010100001101000001011100111100001010011110101110000101011000
0101001101111001001111010110010110001100011001111110001111010100000101000010100111010010111
1010110111000110001101011010101011001110101100110101000101001110010010110111111100000001101
0111000000111010101101110001001001000100001101111011100010010000101010101000111010000001101
1010101011011010110110011010110110011011111110111010011001010111010001100011001111000010100
1000110110101000010100101000010101001001011011100111111010110111000001100001111101110101100
1110100110101011110101110001110110110001001111001000010001100001000110100101100100101100000
0111111100100001101111111000010011000110101110100011001011001101101101011101111101011010011
0001100101010000011000111111011100111001000011111101001011001101011100101101110000010001010
0010110011000011110100001100111110110011100101101110011010010011101100100101010101111110000
0000111111010111101010010011110011001011101111010001101100101101110101111101110110100111011
1010011110001101001011110110001010111110000101000010010001001111111000100001100110110111011
0010011010010000100111001110101001111100110011101010100001001100000100111110001101010101010
0001101110011000000011001100000010100001011110010101100011100001001001010111100010100001100
1010001010100110010111111011100110111000010110100110001111110011000100011110010001110101101
0011111101001100110010110111001101000101001111011000110001000000101011100110111011111010011
0100111000110000101000111110011101110000111001011000101100110100010010010000010111101011100
0101100100100110001101000101100000101100011110101001000100101010010101010111001010100111111
0001001110110010101011100001001010010100101000101111111101110001011101101110011111101100001
0011001011011000111010100101101010000010011001001011101111011000000001100011101001010111100
10001010011011110111111001100110000101011111100011001111111100001110000001100100001000010

样例输出 1

0

数据范围与提示

The sample is generated using RNG0 with s=123. Please note that this test case is only a sample and won't be included in the testing.

Your program will be tested on one test data containing 1000 test cases. Each test case is generated randomly: first randomly pick between RNG0,RNG1,RNG2 (*rng[0],*rng[1],*rng[2]), and randomly pick an integer s between $[0,10^9]$, do srand(s), then call gen() 2000 times and take the outputed sequence. You must answer correctly for at least 990 test cases. It's worth noting that even if you're unsure of the number of some certain test case, you still need to output 0,1 or 2, or you may get Wrong Answer verdict.