Ma trận XOR

Trong một buổi học, giáo sư đã đưa ra một bài toán thú vị cho FullHouse Dev. Họ được yêu cầu phải tìm ma trận vuông đẹp lớn nhất trong một ma trận cho trước.

Bài toán

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 chúng nằm trong ma trận).

Cho ma trận vuông \(A\) kích thước \(n\), mỗi ô có giá trị \(0\) hoặc \(1\). Với \(q\) truy vấn, mỗi truy vấn cho biết ô góc trên trái \((x_1,y_1)\) và ô góc dưới phả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 có thể tìm được 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 tiên của mỗi test case chứa 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 \leq T \leq 10\)
• \(1 \leq n \leq 1000\)
• \(1 \leq q \leq 10^5\)
• \(1 \leq x_1 \leq x_2 \leq n\)
• \(1 \leq y_1 \leq y_2 \leq 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 đầu tiên, ma trận vuông đẹp lớn nhất có kích thước 3x3
• Ở truy vấn thứ hai, ma trận vuông đẹp lớn nhất chỉ có kích thước 1x1