在与wdy的旅途中，魔女和wdy发现了一个山谷，这个山谷可以表示为一个大小为 n×n�×� 的矩阵，在 i� 和 j� 的交点上有一座高度为 ai,j��,� 的山。如果是 ai,j<0��,�<0 ，那么那里有一个湖。

wdy非常怕水，所以魔女需要帮助他：

• 她可以用魔法选择一条水平的山脉区域，并将该区域的每座山的高度增加一米。

更正式地说，她可以选择一个最左边位于 (i,1)(�,�) ，最右边位于 (i,n)(�,�) 的1×n�×�子矩阵 。然后，她可以在 第i(�+�) -th 行的每个元素上加一 。

求魔女使用魔法的最少次数，这样就不会有湖泊了。

第一行包含一个整数 t� ( 1≤t≤2001≤�≤200 ) - 测试用例数。

每个测试用例的描述如下：

• 每个测试用例的第一行包含一个数字 n� ( 1≤n≤1001≤�≤100 )。
• 接下来的每行 n� 都由 n� 个整数组成，中间用空格隔开，这些整数对应山谷中的山高 a� ( −10000≤ai,j≤10000−10000≤��,�≤10000 )。