배송

체스와프 씨는 정사각형 모양의 도시 콰드라토보(Kwadratowo)에서 운송 회사를 운영한다. 방금 새 주문을 받았는데, 반드시 오늘 안에 화물을 실은 트럭을 가능한 한 많이 내보내야 한다. 평소라면 전혀 문제가 되지 않겠지만, 최근 시(市)의 조치가 상황을 복잡하게 만들었다. 혹독한 겨울이 지나며 도로 상태가 크게 나빠지자, 시는 다음 보수 공사 전까지 한시적으로 도로 이용을 제한하기로 했다. 각 도로에는 하루에 몇 번까지 지나갈 수 있는지를 나타내는 수가 하나씩 매겨져 있다.

콰드라토보는 모양이 매우 규칙적이다. 도시의 지도는 한 변이 n개의 거리로 이루어진 정사각형이다. 각 거리는 두 교차로를 잇는다. 따라서 도시 전체에는 $(n+1)^2$개의 교차로가 있으며, n+1개의 행과 n+1개의 열로 놓여 있다. 주민들은 교차로를 두 정수의 쌍으로 부른다. 가장 북서쪽 교차로가 (0, 0)이고 가장 남동쪽 교차로가 (n, n)이며, 첫 번째 좌표는 남쪽으로 얼마나 떨어져 있는지를, 두 번째 좌표는 동쪽으로 얼마나 떨어져 있는지를 나타낸다. 각 교차로에서는 북, 동, 남, 서 방향으로 각각 한 개씩, 최대 네 개의 거리가 뻗어 나가며, 그 방향에 이웃한 교차로가 있을 때에만 존재한다.

체스와프 씨 앞에 놓인 과제는 만만치 않다. 교차로 (0, 0)에서 교차로 (n, n)까지 트럭을 최대 몇 대나 보낼 수 있을까?

첫째 줄에 테스트 케이스의 개수 Z가 주어진다 (Z = 1).

다음 줄에 자연수 n ($1 \le n \le 1000$), 즉 콰드라토보의 가로세로 크기가 주어진다. 이어지는 $2n+1$개의 줄에는 시가 정한 도로 제한값이 북서쪽부터 순서대로 주어진다.

• 홀수 번째 줄(1, 3, ..., $2n+1$번째 줄)에는 n개의 수가 있으며, 이는 한 교차로 행을 따라 놓인 동서 방향 거리들의 제한값이다(맨 위 행인 0번 행부터 맨 아래 행인 n번 행까지 순서대로).
• 짝수 번째 줄(2, 4, ..., $2n$번째 줄)에는 n+1개의 수가 있으며, 이는 인접한 두 교차로 행 사이를 잇는 남북 방향 거리들의 제한값이다.

각 줄 안에서는 서쪽에서 동쪽 순서로 주어진다. 모든 제한값은 1000000010보다 작은 양의 정수이다.

교차로 (0, 0)에서 교차로 (n, n)까지 보낼 수 있는 트럭의 최대 대수를 정수 하나로 출력한다.