hash

Problem Description

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.

Input

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.

Output

For each test case, output a single line "Case #x :y z", where x is the case number, starting from 1. And y z is the answer.

Sample Input

1
0000011100
0000110011
0111111100
0011110010
0110101010
1001001001
0100111110
1111001010
0011101110
1100110100

Sample Output

Case #1 :123456 234567

Source

2017 Multi-University Training Contest - Team 2