中场撸猫
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

\hspace{15pt}好了，猫猫你现在已经完成了新手教程，下面开始[数据删除]Online的实战演练吧~
\hspace{15pt}本题与《B.数数入门》共享部分题目背景，这一部分我们使用特殊的格式标注。
〖引用开始〗
\hspace{15pt}Askalana 搭建了一个 n 层的麻将塔。从上往下数，第 i 层由 i 块麻将组成。每一块麻将上面都刻了一个整数，记第 i 层从左往右数第 j 块麻将上的数字为 a_{i,j}。如下所示：
\begin{array}{c}<br />a_{1,1}\\ <br />a_{2,1} \hspace{20pt} a_{2,2} \\ <br />a_{3,1} \hspace{20pt} a_{3,2} \hspace{20pt} a_{3,3} \\<br />\vdots \hspace{35pt} \vdots \hspace{35pt} \vdots \hspace{35pt} \vdots \\ <br />a_{n,1} \hspace{23pt} a_{n,2} \hspace{23pt} \cdots \hspace{23pt} a_{n,n} <br />\end{array}
\hspace{15pt}除最下层外，每块麻将的左、右两角分别由其两块麻将支撑；如果一座麻将塔中，每一块麻将左下、右下支撑它的麻将上的整数均不小于它自身，那么称这座麻将塔是“平衡的”。更具体地，对于任意的 a_{i,j} \left(1 \leqq i \lt n;\ 1 \leqq j \leqq i\right)，若都有 a_{i, j} \leqq a_{i+1, j} 且 a_{i, j} \leqq a_{i+1, j+1}，那么这座麻将塔是“平衡的”。
〖引用结束〗
\hspace{15pt}教导小猫已经耗尽了 Askalana 单身[数据删除]年的全部魔力，距离大魔法师又远了一步的 Askalana 准备让她的猫进行一些实践。为此，她将 n \times n 块麻将排成了一个 n 行 n 列的矩阵，她想让她的猫从第一行开始，在第 i 行的 n 块麻将中选择 i 块麻将（不需要连续，且不限顺序），作为麻将塔的第 i 层，最终构建出一个“平衡的”麻将塔。
\hspace{15pt}可是猫猫搭的太慢了，Askalana觉得让你闲着有点不太好，于是她想让你快速的回答：猫猫最高可以搭出几层的平衡塔呢？

输入描述:

\hspace{15pt}每个测试文件均包含多组测试数据。第一行输入一个整数 T\left(1\leqq T\leqq 100\right) 代表数据组数，每组测试数据描述如下：
\hspace{15pt}第一行输入一个正整数 n \left(1 \leqq n \leqq 10^3\right) 代表 Askalana 提供的麻将矩阵的大小。
\hspace{15pt}此后 n 行，第 i 行输入 n 个正整数 b_{i,1}, b_{i,2}, \dots, b_{i,n} \left(1 \leqq b_{i,j} \leqq 10^9\right) 代表麻将矩阵中第 i 行的麻将数值。

\hspace{15pt}除此之外，保证单个测试文件的 n 之和不超过 10^3。

输出描述:

\hspace{15pt}对于每一组测试数据，新起一行。输出一个整数，代表猫猫最高可以搭出几层的平衡塔。
示例1

输入

复制 
3
4
6 8 1 7
3 2 9 4
6 4 5 1
9 7 10 8
4
9 8 7 6
5 4 1 3
2 4 1 3
5 1 3 4
3
6 9 9
5 6 9
9 6 9

输出

复制 
4
1
3

说明

\hspace{15pt}对于第一组测试数据，从每一行中选出的麻将使用橙色标注，如公式所示：\begin{bmatrix}<br /> 6 & 8 & {\color{orange}1} & 7 \\<br /> {\color{orange}3} & {\color{orange}2} & 9 & 4 \\<br /> {\color{orange}6} & {\color{orange}4} & {\color{orange}5} & 1 \\<br /> {\color{orange}9} & {\color{orange}7} & {\color{orange}10} & {\color{orange}8}<br />\end{bmatrix}。可以搭建出的麻将塔如公式所示：\begin{array}{c}<br />1\\ <br />3 \quad 2\\ <br />6 \quad 4 \quad 5 \\<br />9 \quad 7 \quad 10 \quad 8<br />\end{array}。

\hspace{15pt}对于第二组测试数据，无论在第一行选择那一块麻将作为麻将塔的第一层，都无法在第二层选择合适的麻将使得麻将塔平衡。所以，猫猫最高可以搭出 1 层平衡塔。

\hspace{15pt}对于第三组测试数据，唯一的选择方案如公式所示：\begin{bmatrix}<br />{\color{orange}6} & 9 & 9 \\<br />5 & {\color{orange}6} & {\color{orange}9} \\<br />{\color{orange}9} & {\color{orange}6} & {\color{orange}9}<br />\end{bmatrix}。特别地，第三层的选择顺序为 6, 9, 9。可以搭建出的麻将塔如公式所示：\begin{array}{c}<br />6\\ <br />6 \quad 9\\ <br />6 \quad 9 \quad 9<br />\end{array}。