You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

【题目描述】

​ 一天，小$L$发现了一个迷宫，他决定去探险。

​ 迷宫可以抽象成一个$n*n$的点阵，左上角为$(1,1)$，右下角为$(n,n)$。每一个点和它在横向和纵向相邻的点之间有一条道路相连。小$L$现在想从$(1,1)$走到$(n,n)$，他只能向右或向下走，即如果小$L$当前在$(i,j)$，那么他下一步能走到$(i+1,j)$或者$(i,j+1)$。显然，小$L$中途不能走出迷宫。

​ 小$L$有一个法力值，初始是$0$。每条道路有一个法力属性。当小$L$经过一条法力属性为$x$的道路时，他的法力值会异或上$x$。小$L$希望自己最终的法力值为$W$，现在他想知道，有多少种方法能做到，两种方法不同当且仅当它们经过的点集不同。

【输入格式】

​ 输入文件名为explore.in。

​ 第一行一个正整数$T$，表示测试点个数。

​ 对于每一个测试点第一行两个数$n,W$，意义见【题面描述】。

​ 接下来$n$行每行$n-1$个数，第$x$行第$y$个数表示连接$(x,y)$和$(x,y+1)$的道路的法力属性。

​ 接下来$n-1$行每行$n$个数，第$x$行第$y$个数表示连接$(x,y)$和$(x+1,y)$的道路的法力属性。

【输出格式】

​ 输出文件名为explore.out。

​ 对于每一个测试点输出一行，即为使最终法力值为$W$的路径条数。

【样例1】

1
2 0
2
3
3 2

2

【样例解释】

​ 有两条可行的路径：

​ $(1,1)->(1,2)->(2,2),2~xor~2=0$

​ $(1,1)->(2,1)->(2,2),3~xor~3=0$

【样例2】

​ 见下发文件。

【数据范围】

​ 对于 $30\%$ 的数据，满足 $n \leq 10$。

​ 另有 $30\%$ 的数据，满足 $所有道路的法力属性 < 1024,W < 1024$。

​ 对于 $100\%$ 的数据，满足 $1 \leq n \leq 20，所有道路的法力属性 < 2^{60},W < 2^{60},1 \leq T \leq 5$。