Chef Ada has a matrix with $N$ rows (numbered $1$ through $N$ from top to bottom) and $N$ columns (numbered $1$ through $N$ from left to right) containing all integers between $1$ and $N^2$ inclusive. For each valid $i$ and $j$, let's denote the cell in the $i$-th row and $j$-th column by $(i,j)$.
Ada wants to sort the matrix in row-major order ― for each valid $i$ and $j$, she wants the cell $(i, j)$ to contain the value $(i-1) \cdot N + j$.
In one operation, Ada should choose an integer $L$ and transpose the submatrix between rows $1$ and $L$ and columns $1$ and $L$ (inclusive). Formally, for each $i$ and $j$ ($1 \le i, j \le L$), the value in the cell $(i, j)$ after this operation is equal to the value in $(j, i)$ before it.
The initial state of the matrix is chosen in such a way that it is possible to sort it using a finite number of operations (possibly zero). Find the smallest number of operations required to sort the matrix.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains a single integer $N$.
- The next $N$ lines describe the matrix. For each valid $i$, the $i$-th of these lines contains $N$ space-separated integers ― the initial values in cells $(i, 1), (i, 2), \ldots, (i, N)$.

-----Output-----
For each test case, print a single line containing one integer ― the smallest number of operations required to sort the matrix.

-----Constraints-----
- $4 \le N \le 64$
- the sum of $N^2$ over all test files does not exceed $3 \cdot 10^5$

-----Subtasks-----
Subtask #1 (10 points):
- $T \le 50$
- $N = 4$
Subtask #2 (90 points): original constraints

-----Example Input-----
1
4
1 2 9 13
5 6 10 14
3 7 11 15
4 8 12 16

-----Example Output-----
2

-----Explanation-----
Example case 1: After the first operation, with $L = 2$, the resulting matrix is
1 5 9 13
2 6 10 14
3 7 11 15
4 8 12 16

After the second operation, with $L = 4$, the matrix becomes sorted
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = '# cook your dish here\nfor i in range(int(input())):\n n = int(input())\n mat = []\n for i in range(n):\n  mat.append([int(j) for j in input().split()])\n # print(mat)\n ans = 0\n t = True\n for i in range(n-1, 0, -1):\n  if t:\n   if mat[0][i] != i+1:\n    t = False\n    ans += 1\n  else:\n   if mat[0][i] == i+1:\n    t = True\n    ans += 1\n print(ans)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13163