You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景：

在经历了一系列莫名其妙的冒险之后，night带着他心爱的小背包来到了一座山的山脚下，在入山口night看见一个牌子上写着登山的规则，“此山上有着许多的积分点，只有上方点位的积分高于所处位置的积分时，才能登上上方积分点；当无法登上上方的点位时，只有正前方的积分等于所处位置的积分时，才能登上正前方积分点；当无法登上正前方积分点时，只有下方点位的积分低于所处位置的积分时，才能登上下方积分点，每登上一个点位都能得到此点位的积分，所登上的分数最高的点位得到的积分是原本的两倍。”night若有所思的点点头，踏上了登山之路。

题目描述：

以矩形数组的左下角为起点，尽力向右上方进发，只有右上方的点位的积分大于目前点位的积分，前进到右上方的点位；当无法登上右上方的点位时，只有正右方的点位的积分等于目前点位的积分，前进到正右方的点位；当无法登上正右方的点位时，只有右下方的点位的积分小于目前点位的积分，前进到右下方点位。超出数组的范围或者无法再前进时结束攀登，请注意攀爬是连续不断的，攀爬所经历的点位都是相邻的。

输入描述：

在第一行输入一个T，代表输入T组数据。

在第二行输入一个N，代表矩形数组的边长。

在2+N行，每行输入N个数，构成N*N的矩形数组。

输出描述：

一行输出，输出night所获得的总积分。

Samples

1

9

6 2 1 8 6 8 1 3 4

1 5 8 7 1 3 6 9 5 

2 4 8 7 2 3 2 1 7

1 7 8 6 2 3 7 1 6

3 5 7 8 9 6 1 4 8

5 7 8 3 9 9 7 8 9

1 3 8 8 8 2 7 7 4

2 3 7 7 7 4 1 6 6

1 6 3 8 9 9 4 1 3

75

1

5

1 1 1 1 1

1 1 1 1 1

1 1 1 1 5

1 9 1 3 1

1 1 1 1 1

28

数据范围：

1 <= N <= 100;

1 <= 点位积分 <= 10;

1s, 1024KiB for each test case.