Qscqesze is busy at data cleaning.
One day,he generates a large matrix by Jenkins one-at-a-time hash:
inline unsigned sfr(unsigned h, unsigned x) {
  return h >> x;
}
int f(LL i, LL j) {
  LL w = i * 1000000ll + j;
  int h = 0;
  for(int k = 0; k < 5; ++k) {
    h += (int) ((w >> (8 * k)) & 255);
    h += (h << 10);
    h ^= sfr(h, 6);
  }
  h += h << 3;
  h ^= sfr(h, 11);
  h += h << 15;
  return sfr(h, 27) & 1;
}
Obviously,it's a 1e6*1e6 matrix.The data is at row i column j is f(i,j).Note that i and j are both numbered from 1.
Then he gets some matrices sized 1e3*1e3 from the matrix above.But he forgets their original postion.Can you help him to find them out?You just are asked to tell Qscqesze the left-top corner's postion.

The first line is the number of test cases T (T<=3). 
Here come with T cases.Each case is consist of 1000 0/1-strings sized 1000.
For convenience,the sample input is 10*10.And the real testcase is 1e3*1e3.