UpRace, dự án chạy bộ vì cộng đồng do VNG đề xuất, đang càng ngày càng có sức lan tỏa và ảnh hưởng trong cộng đồng. Năm nay, VNG đã đề xuất thêm một cuộc thi đặc biệt, Robot UpRace, nhằm khuyến khích phong trào tìm hiểu về trí tuệ nhân tạo và tự động hóa ở thế hệ trẻ Việt Nam.

Các robot sẽ tiến hành cuộc đua trên một lưới chữ nhật kích thước \(n\) \(\times\) \(n\). Các dòng được đánh số từ \(1\), các cột cũng được đánh số từ \(1\) đến \(n\). Ô nằm tại dòng \(i\) và cột \(j\) được gọi là ô \((i, j)\). Mỗi ô đều được ghi một số nguyên từ \(1\) đến \(n^2\).

Phần thi của một Robot sẽ bắt đầu khi robot xuất phát tại ô \((1, 1)\), và sẽ kết thúc khi robot di chuyển đến ô \((n, n)\). Ở mỗi bước, robot chỉ có thể đi đến một trong bốn ô kề cạnh với ô hiện tại. Robot không được phép di chuyển ra ngoài lưới chữ nhật. Ban tổ chức định nghĩa điểm số của một phần thi là số nguyên dương nhỏ nhất không xuất hiện tại các ô mà robot đi qua trong phần thi đó. Ban tổ chức sẽ xếp hạng các đội dựa vào điểm số của phần thi, điểm số càng nhỏ thì thứ hạng càng cao.

Hãy tìm điểm số nhỏ nhất có thể đạt được trong một phần thi.

\(\\\)

Input

Bộ dữ liệu gồm nhiều test case. Dòng đầu tiên của bộ dữ liệu chứa số nguyên dương \(t\) \((1 \leq t \leq 100)\) là số lượng test case. Mô tả của mỗi test case như sau.

Dòng đầu tiên chứa số nguyên \(n\) \(2 \leq n \leq 2000\) - kích thước của lưới hình chữ nhật.

Dòng thứ \(i\) trong số \(n\) dòng tiếp theo gồm \(n\) số nguyên \(a_{i,1}, a_{i,2}, \ldots, a_{i,n} \space (1 \leq a_{i,j} \leq n^2)\) - các số được ghi tại các ô trên dòng \(i\).

Dữ liệu đảm bảo rằng tổng \(n^2\) trong tất cả các test case không vượt quá \(4 \cdot 10^6\).

\(\\\)

Output

Với mỗi test case, hãy in ra điểm số nhỏ nhất có thể đạt được trong một phần thi.

\(\\\)

Scoring

\(\\\)

Sample Input 1

2
3
3 1 2
1 3 2
1 1 4
2
2 3
3 4

Sample Output 1

2
1

Note

Ở ví dụ thứ nhất, một trong số các phần thi có điểm số nhỏ nhất là \((1, 1) \to (1, 2) \to (2, 2) \to (2, 1) \to (3, 1) \to (3, 2) \to (3, 3).\) Giá trị của các ô nằm trên đường đi là \([3, 1, 3, 1, 1, 1, 4]\) và điểm số của phần thi là \(2.\)

Ở ví dụ thứ hai, một trong số các phần thi có điểm số nhỏ nhất là \((1, 1) \to (1, 2) \to (2, 2).\) Giá trị của các ô trên đường đi là \([2, 3, 4]\) và điểm số của phần thi là \(1.\)

Nguồn: Code Tour 2024