题目描述

运动会开始了。

1 班的同学们全都搬来了凳子，除了运动员去各自赛场参赛外，其他同学均已落座。

3 班的同学们全都忘了搬凳子，于是来到 1 班借凳子。3 班没有运动员。

每位同学只会将自己的凳子借给自己的朋友。

比如：

A 和 B 都是 1 班的同学，其中 A 是运动员，去参加比赛了。

C 是 3 班的同学。

C 与 B 是朋友，与 A 不是朋友。

B 与 A 是朋友。

C 来找 B 借凳子。B 可以把自己的凳子借给 C，然后自己坐到 A 的凳子上。

如果 B 把自己的凳子借出去，他只能坐到自己朋友的凳子上。

如果 C 与 A 是朋友，A 是运动员，去参加比赛了，则 C 可以直接借走 A 的凳子。

现在给出相关信息，问：除了运动员外，是否每个人都有凳子坐？

输入格式

第一行：一个整数 $T$，表示数据组数。对于每组数据：

• 第一行：一个整数 $N$ 表示 1 班和 3 班的总人数。
• 接下来一行：$N$ 个整数，要么为 0，要么为 1。其中第 $i$ 个数为 $1$ 表示第 $i$ 个同学是 1 班的，为 $0$ 则表示该同学是 3 班的。
• 接下来一行：$N$ 个整数，要么为 0，要么为 1。其中第 $i$ 个数为 $1$ 表示第 $i$ 个同学是运动员，为 $0$ 则表示该同学不是运动员。（注意：如果第 $i$ 个同学是 3 班的，那么对应的这个整数则没有意义。）
• 接下来是一个 $N×N$ 的 01 矩阵 A，其中 Aij=1 表示第 i 个同学和第 j 个同学是朋友，否则表示不是朋友。数据保证 Aij=Aji。Aii 的值没有意义。

输出格式

每组数据的答案占一行：如果能使得每个人都能有凳子坐，则输出 1，否则输出 0。

样例输入

2
3
1 1 0
0 1 0
0 1 1
1 0 0
1 0 0
3
1 1 0
0 1 0
1 0 1
0 0 0
1 0 1

样例输出

1
0

提示

$30\%$ 的数据： $1 \le N \le 12$。

$100\%$ 的数据： $1 \le T \le 20$，$1 \le N \le 50$。