作为对行为不端的惩罚，Byteasar 需要计算一个神秘且复杂的布尔值函数 $F(x,y)$。该函数针对一对正整数序列 $x=(x_1,…,x_n)$ 和 $y=(y_1,…,y_m)$ 定义如下：

boolean F(x,y)
if W(x)≠W(y) then return 0
else if |W(x)|=|W(y)|=1 then return 1
else return F(p(x),p(y)) ∧ F(s(x),s(y)).

其中：

• $W(x)$ 表示序列 $x$ 中元素的集合（元素的顺序和重复次数无关），
• $p(x)$ 表示序列 $x$ 的最长前缀（任意长度的初始部分），满足 $W(x) \neq W(p(x))$，
• $s(x)$ 表示序列 $x$ 的最长后缀（任意长度的末尾部分），满足 $W(x) \neq W(s(x))$，
• $∧$ 表示逻辑与运算，1 代表真，0 代表假，$|z|$ 表示集合 $z$ 的基数。

例如，对于序列 $x=(2,3,7,2,7,4,7,2,4)$，我们有：$W(x)=\{2,3,4,7\}$，$p(x)=(2,3,7,2,7)$，$s(x)=(7,2,7,4,7,2,4)$。对于非常大的数据，直接根据定义计算函数 $F$ 的程序在任何标准下都太慢了。因此，你需要尽可能快地完成这些计算。

编写一个程序，从标准输入读取若干对序列 $(x,y)$，并为每一对输入输出 $F(x,y)$ 的值。

标准输入的第一行包含一个整数 $k$ ($1 \le k \le 13$)，表示要分析的序列对数。接下来的 $3k$ 行包含测试用例的描述。每个描述的第一行包含两个整数 $n$ 和 $m$ ($1 \le n,m \le 100\,000$)，由空格分隔，分别表示第一个和第二个序列的长度。第二行包含 $n$ 个整数 $x_i$ ($1 \le x_i \le 100$)，构成序列 $x$，由空格分隔。第三行包含 $m$ 个整数 $y_i$ ($1 \le y_i \le 100$)，构成序列 $y$，由空格分隔。

输出应包含恰好 $k$ 行；第 $i$ 行（对于 $1 \le i \le k$）应包含一个整数——$0$ 或 $1$——即第 $i$ 个测试用例中 $F(x,y)$ 的值。

样例

输入格式 1

2
4 5
3 1 2 1
1 3 1 2 1
7 7
1 1 2 1 2 1 3
1 1 2 1 3 1 3

输出格式 1

0
1