RNGs
题号：NC26276
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

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
00111011000010101110100010010000000111010010100001101111001110001100100110100000011100110010010010101100011001110000010000010100001101000001011100111100001010011110101110000101011000010100110111100100111101011001011000110001100111111000111101010000010100001010011101001011110101101110001100011010110101010110011101011001101010001010011100100101101111111000000011010111000000111010101101110001001001000100001101111011100010010000101010101000111010000001101101010101101101011011001101011011001101111111011101001100101011101000110001100111100001010010001101101010000101001010000101010010010110111001111110101101110000011000011111011101011001110100110101011110101110001110110110001001111001000010001100001000110100101100100101100000011111110010000110111111100001001100011010111010001100101100110110110101110111110101101001100011001010100000110001111110111001110010000111111010010110011010111001011011100000100010100010110011000011110100001100111110110011100101101110011010010011101100100101010101111110000000011111101011110101001001111001100101110111101000110110010110111010111110111011010011101110100111100011010010111101100010101111100001010000100100010011111110001000011001101101110110010011010010000100111001110101001111100110011101010100001001100000100111110001101010101010000110111001100000001100110000001010000101111001010110001110000100100101011110001010000110010100010101001100101111110111001101110000101101001100011111100110001000111100100011101011010011111101001100110010110111001101000101001111011000110001000000101011100110111011111010011010011100011000010100011111001110111000011100101100010110011010001001001000001011110101110001011001001001100011010001011000001011000111101010010001001010100101010101110010101001111110001001110110010101011100001001010010100101000101111111101110001011101101110011111101100001001100101101100011101010010110101000001001100100101110111101100000000110001110100101011110010001010011011110111111001100110000101011111100011001111111100001110000001100100001000010

输出

复制 
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 , 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.