Circular land is an $2n \times 2n$ grid. Rows of this grid are numbered by integers from $1$ to $2n$ from top to bottom and columns of this grid are numbered by integers from $1$ to $2n$ from left to right. The cell $(x, y)$ is the cell on the intersection of row $x$ and column $y$ for $1 \leq x \leq 2n$ and $1 \leq y \leq 2n$.

There are $n^2$ of your friends in the top left corner of the grid. That is, in each cell $(x, y)$ with $1 \leq x, y \leq n$ there is exactly one friend. Some of the other cells are covered with snow.

Your friends want to get to the bottom right corner of the grid. For this in each cell $(x, y)$ with $n+1 \leq x, y \leq 2n$ there should be exactly one friend. It doesn't matter in what cell each of friends will be.

You have decided to help your friends to get to the bottom right corner of the grid.

For this, you can give instructions of the following types:

You select a row $x$. All friends in this row should move to the next cell in this row. That is, friend from the cell $(x, y)$ with $1 \leq y < 2n$ will move to the cell $(x, y + 1)$ and friend from the cell $(x, 2n)$ will move to the cell $(x, 1)$.

You select a row $x$. All friends in this row should move to the previous cell in this row. That is, friend from the cell $(x, y)$ with $1 < y \leq 2n$ will move to the cell $(x, y - 1)$ and friend from the cell $(x, 1)$ will move to the cell $(x, 2n)$.

You select a column $y$. All friends in this column should move to the next cell in this column. That is, friend from the cell $(x, y)$ with $1 \leq x < 2n$ will move to the cell $(x + 1, y)$ and friend from the cell $(2n, y)$ will move to the cell $(1, y)$.

You select a column $y$. All friends in this column should move to the previous cell in this column. That is, friend from the cell $(x, y)$ with $1 < x \leq 2n$ will move to the cell $(x - 1, y)$ and friend from the cell $(1, y)$ will move to the cell $(2n, y)$.

Note how friends on the grid border behave in these instructions.

Example of applying the third operation to the second column. Here, colorful circles denote your friends and blue cells are covered with snow.

You can give such instructions any number of times. You can give instructions of different types. If after any instruction one of your friends is in the cell covered with snow he becomes ill.

In order to save your friends you can remove snow from some cells before giving the first instruction:

You can select the cell $(x, y)$ that is covered with snow now and remove snow from this cell for $c_{x, y}$ coins.

You can do this operation any number of times.

You want to spend the minimal number of coins and give some instructions to your friends. After this, all your friends should be in the bottom right corner of the grid and none of them should be ill.

Please, find how many coins you will spend.


-----Input-----

The first line contains a single integer $t$ ($1 \leq t \leq 100$) — the number of test cases.

The first line of each test case contains the single integer $n$ ($1 \leq n \leq 250$).

Each of the next $2n$ lines contains $2n$ integers $c_{i, 1}, c_{i, 2}, \ldots, c_{i, 2n}$ ($0 \leq c_{i, j} \leq 10^9$) — costs of removing snow from cells. If $c_{i, j} = 0$ for some $i, j$ than there is no snow in cell $(i, j)$. Otherwise, cell $(i, j)$ is covered with snow.

It is guaranteed that $c_{i, j} = 0$ for $1 \leq i, j \leq n$.

It is guaranteed that the sum of $n$ over all test cases doesn't exceed $250$.


-----Output-----

For each test case output one integer — the minimal number of coins you should spend.


-----Examples-----

Input
4
1
0 8
1 99
2
0 0 0 0
0 0 0 0
9 9 2 2
9 9 9 9
2
0 0 4 2
0 0 2 4
4 2 4 2
2 4 2 4
4
0 0 0 0 0 0 0 2
0 0 0 0 0 0 2 0
0 0 0 0 0 2 0 0
0 0 0 0 2 0 0 0
0 0 0 2 2 0 2 2
0 0 2 0 1 6 2 1
0 2 0 0 2 4 7 4
2 0 0 0 2 0 1 6
Output
100
22
14
42


-----Note-----

In the first test case you can remove snow from the cells $(2, 1)$ and $(2, 2)$ for $100$ coins. Then you can give instructions

All friends in the first collum should move to the previous cell. After this, your friend will be in the cell $(2, 1)$.

All friends in the second row should move to the next cell. After this, your friend will be in the cell $(2, 2)$.

In the second test case you can remove all snow from the columns $3$ and $4$ for $22$ coins. Then you can give instructions

All friends in the first row should move to the next cell.

All friends in the first row should move to the next cell.

All friends in the second row should move to the next cell.

All friends in the second row should move to the next cell.

All friends in the third column should move to the next cell.

All friends in the third column should move to the next cell.

All friends in the fourth column should move to the next cell.

All friends in the fourth column should move to the next cell.

It can be shown that none of the friends will become ill and that it is impossible to spend less coins.

Difficulty: HARD
Tags: Greedy algorithms

Mathematics

Constructive algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	c = []
	coins = 0
	for i in range(2 * n):
		if i < n:
			c.append(list(map(int, input().split())))
		else:
			k = list(map(int, input().split()))
			coins = coins + sum(k[n:])
			c.append(k)
	add = min(c[0][n], c[0][-1], c[n - 1][n], c[n - 1][-1])
	add = min(add, c[n][0], c[n][n - 1], c[-1][0], c[-1][n - 1])
	print(coins + add)


from collections import Counter, defaultdict, deque
import heapq
import bisect
from sys import stdin, stdout
from itertools import repeat
import math, random

def inp(force_list=False):
	re = list(map(int, input().split()))
	if len(re) == 1 and (not force_list):
		return re[0]
	return re

def inst():
	return input().strip()

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
mod = 1000000007

def my_main():
	kase = inp()
	pans = []
	mx = int(1e+17)
	for ka in range(kase):
		n = inp()
		da = [inp() for i in range(2 * n)]
		ans = 0
		for i in range(n, 2 * n):
			for j in range(n, 2 * n):
				ans += da[i][j]
		ans += min(da[0][n], da[0][2 * n - 1], da[n - 1][n], da[n - 1][2 * n - 1], da[n][0], da[n][n - 1], da[2 * n - 1][0], da[2 * n - 1][n - 1])
		pans.append(str(ans))
	print('\n'.join(pans))
my_main()


import sys
sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline
linput = lambda : list(map(int, input().split()))
iinput = lambda : map(int, input().split())
n = 0

def solve():
	global dd, visited, arr, dp, n
	n = int(input())
	arr = [linput() for __ in range(2 * n)]
	answer = 0
	for i in range(n, 2 * n):
		for j in range(n, 2 * n):
			answer += arr[i][j]
	answer += min(arr[n - 1][2 * n - 1], arr[2 * n - 1][n - 1], arr[n - 1][n], arr[n][n - 1], arr[0][n], arr[n][0], arr[0][2 * n - 1], arr[2 * n - 1][0])
	print(answer)
for __ in range(int(input())):
	solve()


from sys import stdin, stdout

def input():
	return stdin.readline().strip('\n')
t = int(input())
for _ in range(t):
	n = int(input())
	mins = set()
	cost = 0
	for x in range(2 * n):
		c = list(map(int, input().split()))
		if x in {0, n - 1}:
			mins.add(c[n])
			mins.add(c[-1])
		if x in {n, 2 * n - 1}:
			mins.add(c[0])
			mins.add(c[n - 1])
		if x >= n:
			cost += sum(c[n:])
	print(cost + min(mins))


import sys
from collections import deque
import heapq
import bisect
import copy
MOD = 1000000007
NO = lambda : print('NO')
YES = lambda : print('YES')
_1 = lambda : print(-1)
ari = lambda : [int(_) for _ in input().split()]
cin = lambda : int(input())
cis = lambda : input()
show = lambda x: print(x)
fast = lambda : sys.stdin.readline()
test_case = 1
test_case = int(input())
sys.setrecursionlimit(10 ** 6)

def ans():
	n = cin()
	costneed = 0
	mat = []
	for i in range(n * 2):
		mat.append(ari())
	for i in range(n, 2 * n):
		for j in range(n, 2 * n):
			costneed += mat[i][j]
	end = 2 * n - 1
	corner = [(n - 1, n), (n - 1, end), (n, 0), (n, n - 1), (end, 0), (end, n - 1), (0, n), (0, end)]
	maxi = float('inf')
	for (x, y) in corner:
		maxi = min(maxi, mat[x][y])
	print(maxi + costneed)
	return
for _ in range(test_case):
	ans()


import sys
input = sys.stdin.readline
t = int(input())
for i in range(t):
	n = int(input())
	mat = []
	for i in range(2 * n):
		mat.append([int(x) for x in input().split()])
	s = 0
	for i in range(n, 2 * n):
		for j in range(n, 2 * n):
			s += mat[i][j]
	ans = min(mat[n - 1][n], mat[n][n - 1], mat[0][2 * n - 1], mat[2 * n - 1][0], mat[n - 1][2 * n - 1], mat[2 * n - 1][n - 1], mat[n][0], mat[0][n])
	print(s + ans)


import math
for _ in range(int(input())):
	n = int(input())
	data = []
	for i in range(2 * n):
		data.append(list(map(int, input().split())))
	total = 0
	for x in range(n, 2 * n):
		for y in range(n, 2 * n):
			total += data[x][y]
	special = min(data[0][n], data[0][-1], data[n - 1][n], data[n - 1][-1])
	special = min(special, data[n][0], data[n][n - 1], data[-1][0], data[-1][n - 1])
	print(total + special)


t = int(input())
for _ in range(t):
	n = int(input())
	c = [[int(i) for i in input().split()] for j in range(2 * n)]
	a = min(c[0][n], c[n][0], c[2 * n - 1][0], c[0][2 * n - 1], c[n - 1][2 * n - 1], c[2 * n - 1][n - 1], c[n][n - 1], c[n - 1][n])
	for i in range(n):
		for j in range(n):
			a += c[i + n][j + n]
	print(a)


INF = 10 ** 20
for _ in range(int(input())):
	n = int(input())
	m = 2 * n
	mtx = [[int(x) for x in input().split()] for i in range(m)]
	finish_cost = 0
	for i in range(n):
		for j in range(n):
			finish_cost += mtx[i + n][j + n]
			mtx[i + n][j + n] = 0
	add_cost = INF
	for cell in ((n, 0), (-1, 0), (n, n - 1), (-1, n - 1), (0, n), (n - 1, n), (0, -1), (n - 1, -1)):
		add_cost = min(add_cost, mtx[cell[0]][cell[1]])
	print(finish_cost + add_cost)


from sys import stdin
ints = (int(i) for i in stdin.read().split())
t = next(ints)
for _ in range(t):
	n = next(ints)
	cost = []
	for _ in range(2 * n):
		row = [next(ints) for _ in range(2 * n)]
		cost.append(row)
	ans = min((cost[i][j] for (i, j) in [(n, n - 1), (n - 1, n), (2 * n - 1, 0), (0, 2 * n - 1), (0, n), (n, 0), (n - 1, 2 * n - 1), (2 * n - 1, n - 1)]))
	for i in range(n, 2 * n):
		for j in range(n, 2 * n):
			ans += cost[i][j]
	print(ans)