Consider a grid graph with $n$ rows and $n$ columns. Let the cell in row $x$ and column $y$ be $(x,y)$. There exists a directed edge from $(x,y)$ to $(x+1,y)$, with non-negative integer value $d_{x,y}$, for all $1\le x < n, 1\le y \le n$, and there also exists a directed edge from $(x,y)$ to $(x,y+1)$, with non-negative integer value $r_{x,y}$, for all $1\le x \le n, 1\le y < n$.

Initially, you are at $(1,1)$, with an empty set $S$. You need to walk along the edges and eventually reach $(n,n)$. Whenever you pass an edge, its value will be inserted into $S$. Please maximize the MEX$^{\text{∗}}$ of $S$ when you reach $(n,n)$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\le t\le100$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2\le n\le20$) — the number of rows and columns.

Each of the next $n-1$ lines contains $n$ integers separated by single spaces — the matrix $d$ ($0\le d_{x,y}\le 2n-2$).

Each of the next $n$ lines contains $n-1$ integers separated by single spaces — the matrix $r$ ($0\le r_{x,y}\le 2n-2$).

It is guaranteed that the sum of all $n^3$ does not exceed $8000$.

Output

For each test case, print a single integer — the maximum MEX of $S$ when you reach $(n,n)$.

见题面 Input 部分

见题面 Output 部分

In the first test case, the grid graph and one of the optimal paths are as follows:

In the second test case, the grid graph and one of the optimal paths are as follows: