Little X lives in (1,1),and little Y lives in (N,N).One day they decide to meet each other.However, the road is full of danger. They can only go to adjacent cells and take time that is equal to the value on the cell.Please tell them the minimum time they should take.

There is a T at the beginning of file, show that there is T case follow.
For every test case, the first line contain one integer N.Then come two N * N matrices A and B.(1000 >= N >= 2)
  If little X wants to go to (i,j),he will spend A(i,j) on moving to adjacent cell (i,j).
  If little Y wants to go to (i,j),he will spend B(i,j) on moving to adjacent cell (i,j).

0<=A(i,j)<=10  0<=B(i,j)<=10

For every case,print the minimum time in one line.