Problem Description

There are $n \times n$ cells on a grid, the top-left cell is at $(1,1)$ while the bottom-right cell is at $(n,n)$. You start at $(1,1)$ and move to $(n,n)$. At any cell $(i,j)$, you can move to $(i+1,j)$ or $(i,j+1)$, provided that you don't move out of the grid. Clearly, you will make exactly $2n-2$ steps.

When you are at cell $(i,j)$, including the starting point $(1,1)$ and the destination $(n,n)$, you can take all the $a_{i,j}$ diamonds at this cell, and have a chance to raise the price of each diamond by $b_{i,j}$ dollars. You will sell all the diamonds you have with the final price in the end, and your goal is to choose the optimal path that will maximize your profits. Note that initially the price of each diamond is zero, and you have nothing to sell.

Input

The first line contains a single integer $T$ ($1 \leq T \leq 10$), the number of test cases. For each test case:

The first line contains a single integer $n$ ($1 \leq n \leq 100$), denoting the size of the grid.

Each of the following $n$ lines contains $n$ integers, the $i$-th line contains $a_{i,1},a_{i,2},\dots,a_{i,n}$ ($1\leq a_{i,j}\leq 10^6$), denoting the number of diamonds in each cell.

Each of the following $n$ lines contains $n$ integers, the $i$-th line contains $b_{i,1},b_{i,2},\dots,b_{i,n}$ ($1\leq b_{i,j}\leq 10^6$), denoting how much you can raise the price in each cell.

It is guaranteed that all the values of $a_{i,j}$ and $b_{i,j}$ are chosen uniformly at random from integers in $[1,10^6]$. The randomness condition does not apply to the sample test case, but your solution must pass the sample as well.

Output

For each test case, output a single line containing an integer: the maximum number of dollars you can earn by selling diamonds.

1
4
2 3 1 5
6 3 2 4
3 5 1 4
5 2 4 1
3 2 5 1
2 4 3 5
1 2 3 4
4 3 5 3

528