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 or 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

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

Limitation

1s, 1024KiB for each test case.