Background

粽子必须是甜的！

粽子必须是咸的！

每逢每年的端午节，上帝都会听到无穷无尽的争吵声，耳朵都磨出茧子了

于是上帝挑选了两个不幸的代表，小 Z 和小 L

决定举行一场不公平的比赛，来决定粽子是甜的还是咸的

Description

上帝思来想去决定通过一个博弈小游戏决定粽子的味道

有一个整数 $x$ 的初始值为 $0$

现存在一个长度为 $N$ 的正整数数列 $A$ ，其中第 $i$ 个数为 $A_{i}$

游戏一共进行 $N$ 轮，给定一个 $01$ 字符串 $S$ ,若$S[i]=0$ 则第 $i$ 轮小 Z 进行操作

若 $S[i]=1$ 则第 $i$ 轮小 L 进行操作

每轮操作可选择对 $x$ 进行异或操作使得 $x=x⊕A_{i}$，或选择不进行任何操作，保 $x$ 原值

若游戏结束后 $x==0$ 则小 Z 获胜，输出 $0$；否则为小 L 获胜，输出 $1$

虽然明知道这个比赛并不公平，但小 Z 和小 L 仍然以最佳水平来发挥，你能找出获胜的那个吗

Format

Input

一行包含一个正整数 $T$ ，表示共有 $T$ 组测试数据

$(1 \leq T \leq 100)$

每组测试数据包括三行

$第一行一个正整数$ $N$ $表示游戏总轮数$ $(1 \leq N \leq 200)$

第二行包含 $N$ 个正整数 $A_{1} A_{2} ... A_{N}$

以空格间隔，$(1 \leq A_{i} \leq 10^{18})$

第三行包含一个 $01$ 字符串 $S$ $(S_{i} = 0/1)$.

Output

对于每组测试数据输出答案 $0$ 或 $1$,每个答案单独占一行

Samples

3
2
1 2
10
2
1 1
10
6
2 3 4 5 6 7
111000

1
0
0

虽然算出答案好像还是不能决定粽子的味道 但起码上帝不会眼烦了