Ma Trận XOR

Trong một buổi dạo chơi ở quảng trường, FullHouse Dev bắt gặp một bài toán thú vị về ma trận. Họ được yêu cầu tìm ma trận vuông đẹp lớn nhất trong một ma trận cho trước, với điều kiện XOR của mọi cặp ô liền kề phải bằng \(1\).

Bài toán

Một ma trận vuông kích thước \(n\) được gọi là đẹp nếu phép XOR của mọi cặp ô liền kề bằng \(1\). Hai ô được coi là liền kề nếu chúng có chung cạnh. Với ô \((i,j)\), các ô \((i-1,j)\), \((i+1,j)\), \((i,j-1)\), và \((i,j+1)\) được coi là liền kề (nếu tồn tại trong ma trận).

Cho ma trận \(A\) kích thước \(n × n\), mỗi ô chứa giá trị \(0\) hoặc \(1\). Với \(Q\) truy vấn, mỗi truy vấn cho biết ô trái trên \((x_1,y_1)\) và ô phải dưới \((x_2,y_2)\) của một ma trận con, hãy tìm kích thước cạnh của ma trận vuông đẹp lớn nhất nằm trong ma trận con đó.

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(T\) - số lượng test case
• Dòng đầu của mỗi test case chứa một số nguyên \(n\) - kích thước ma trận
• \(n\) dòng tiếp theo, mỗi dòng chứa \(n\) số nguyên (0 hoặc 1) mô tả ma trận
• Dòng tiếp theo chứa số nguyên \(Q\) - số lượng truy vấn
• \(Q\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(x_1\), \(y_1\), \(x_2\), \(y_2\)

OUTPUT FORMAT:

• Với mỗi truy vấn, in ra một dòng duy nhất là kích thước cạnh của ma trận vuông đẹp lớn nhất có thể tìm được

Ràng buộc:

• \(1 ≤ T ≤ 10\)
• \(1 ≤ n ≤ 1000\)
• \(1 ≤ Q ≤ 10^5\)
• \(1 ≤ x_1 ≤ x_2 ≤ n\)
• \(1 ≤ y_1 ≤ y_2 ≤ n\)

Ví dụ

INPUT

1
6
1 0 1 0 0 0
0 0 0 0 1 1
1 0 1 0 1 1
1 1 0 1 0 0
0 0 1 0 1 1
1 1 0 0 1 0
2
2 2 6 6
3 5 5 6

OUTPUT

3
1

Giải thích

• Ở truy vấn thứ nhất, ma trận vuông đẹp lớn nhất có kích thước 3×3
• Ở truy vấn thứ hai, ma trận vuông đẹp lớn nhất có kích thước 1×1