题目描述

Mike 和 Joi 在玩一个游戏，他们各有一个长度为 $n$ 的数组，Mike 的数组叫 $a$，Joi 的数组叫 $b$。 已知他们这 $2n$ 个数互不相同，设这 $2n$ 个数构成的集合为 $S$。 现在他们想知道，可以构成多少对 $(i,j)$ 满足 $a_i \oplus b_i \in S$。

当为奇数时，输出 1!，表示 Mike 获胜；当为偶数时，输出 0!，表示 Joi 获胜。请根据题目给出的数据输出结果。

输入格式

第一行一个整数 $T$，表示数据组数。

每组数据内，第一行一个正整数 $n$。

每组数据内，第二行 $n$ 个正整数，表示数组 $a$。

每组数据内，第三行 $n$ 个正整数，表示数组 $b$。

输出格式

输出 $T$ 行，每行一个字符串 0! 或者 1!，表示谁胜利了。

样例

1
3
1 2 3
4 5 6

0!

$1\oplus 4=5$，属于；$1\oplus 5=4$，属于；$1\oplus 6=7$，不属于；

$2\oplus 4=6$，属于；$2\oplus 5=7$，不属于；$2\oplus 6=4$，属于；

$3\oplus 4=7$，不属于；$3\oplus 5=6$，属于；$3\oplus 6=5$，属于。

共 $6$ 对 $(i,j)$ 满足条件，输出 0!。

数据范围

这里用 $v$ 表示数组中最大的数字。

对于前 $30\%$ 的数据，$n\le 10$。

对于前 $70\%$ 的数据，$n\le 2000$。

对于前 $90\%$ 的数据，$v\le 10^6$。

对于 $100\%$ 的数据，$n\le 2\times 10^5$，$v\le 10^9$，$T\le 3$。