#P1908. 下三角矩阵

下三角矩阵

给定一个由0和1组成的矩阵。只允许交换相邻的两行,要把矩阵转化成下三角矩阵(主对角线上方的元素都是0),最少需要交换几次?输入的矩阵保证总能转化成下三角矩阵。

Input

多组测试数据。
每组测试数据第一行为一个整数n(1 <= n < 1000),表示矩阵的大小为n*n;
接下来n行,每行有n个数表示这个矩阵。

Output

输出最小需要交换的次数,单独占一行。

Sample Input

3
0 0 1
1 0 0
0 1 0

Sample Output

2

HINT

Source