题目描述

聪明的 $CRY$ 拿到了 $n$ 个命题标号为 $1$ 到 $n$，他一眼就看出来很多很多命题间的逻辑关系，这些关系分为两种，第一种：若命题 $A$ 成立则命题 $B$ 成立；第二种：若命题 $A$ 成立不易直接判断命题 $B$ 是否成立 。剩余的命题间是否有逻辑关系，他还没有算~

现在问，你至少需要再推导多少个逻辑关系才能知道：若命题 $1$ 成立则命题 $n$ 成立？

数据保证一定可以推导出若干逻辑关系后使得 “若命题 $1$ 成立则命题 $n$ 成立” 。

输入格式

第一行一个整数 $T(1\leq T \leq 5)$ 表示数据组数。

对于每组测试数据，第一行一个整数 $n(2\leq n\leq 400)$，表示命题个数。

接下来 $n$ 行每行 $n$ 个整数：

第 $i$ 行的第 $j$ 个数可能为 $-1,\ 0,\ 1$ 中的一个。$-1$ 表示命题 $i$ 不可以直接推出命题 $j$ ；$1$ 表示命题 $i$ 可以推出命题 $j$ 成立；$0$ 表示 $i,\ j$ 之间的关系还等待你来推导。

数据保证 $i=j$ 时第 $i$ 行第 $j$ 个数一定为 $1$，表示命题显然一定可以推导出自身成立。

输出格式

每组数据输出一行。

一个整数表示至少需要再推导多少个逻辑关系才能知道：若命题 $1$ 成立则命题 $n$ 成立。

若无法实现：命题 $1$ 成立则命题 $n$ 成立，则输出 $-1$。

样例

样例输入

1
3
1 1 0
-1 1 1
0 0 1

样例输出

0