Problem: There are two persons, numbered 0 and 1, and a variable x whose initial value is 0. The two persons now play a game. The game is played in N rounds. The following should be done in the i-th round (1 \leq i \leq N):

* Person S_i does one of the following:
* Replace x with x \oplus A_i, where \oplus represents bitwise XOR.
* Do nothing.



Person 0 aims to have x=0 at the end of the game, while Person 1 aims to have x \neq 0 at the end of the game.

Determine whether x becomes 0 at the end of the game when the two persons play optimally.

Solve T test cases for each input file.

Constraints

* 1 \leq T \leq 100
* 1 \leq N \leq 200
* 1 \leq A_i \leq 10^{18}
* S is a string of length N consisting of `0` and `1`.
* All numbers in input are integers.

Input

Input is given from Standard Input in the following format. The first line is as follows:


T


Then, T test cases follow. Each test case is given in the following format:


N
A_1 A_2 \cdots A_N
S


Output

For each test case, print a line containing `0` if x becomes 0 at the end of the game, and `1` otherwise.

Example

Input

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


Output

1
0
0

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	
	static long[] set;
	static int size;
	
	static void add(long val) {
		long me = Long.highestOneBit(val);
		for (int i = size - 1; i >= 0; i--) {
			long bit = Long.highestOneBit(set[i]);
			if (me == bit) {
				val ^= set[i];
				me = Long.highestOneBit(val);
			}
		}
		if (val != 0) {
			set[size++] = val;
			Arrays.sort(set, 0, size);
		}
	}
	
	static boolean canRemove(long val) {
		long me = Long.highestOneBit(val);
		for (int i = size - 1; i >= 0; i--) {
			long bit = Long.highestOneBit(set[i]);
			if (me == bit) {
				val ^= set[i];
				if (val == 0) {
					return true;
				}
				me = Long.highestOneBit(val);
			}
		}
		return false;
	}
	
	
	public static void main(String[] args) throws IOException {
		MyScanner sc = new MyScanner();
		PrintWriter out = new PrintWriter(System.out);
		int T = sc.nextInt();
		set = new long[70];
		for (int caze = 0; caze < T; caze++) {
			int N = sc.nextInt();
			long[] vals = new long[N];
			for (int i = 0; i < N; i++) {
				vals[i] = sc.nextLong();
			}
			char[] S = sc.next().toCharArray();
			size = 0;
			
			boolean zero = true;
			for (int i = N - 1; i >= 0; i--) {
				if (S[i] == '0') {
					add(vals[i]);
				} else {
					if (!canRemove(vals[i])) {
						zero = false;
					}
				}
			}
			out.println(zero ? 0 : 1);
		}
		
		out.flush();
	}
	
	static class MyScanner {
		private BufferedReader br;
		private StringTokenizer tokenizer;
		
		public MyScanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		
		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}
		
		public int nextInt() {
			return Integer.parseInt(next());
		}
		
		public long nextLong() {
			return Long.parseLong(next());
		}
	}
}