Gellyfish and Flower are playing a game.

The game consists of two arrays of $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ and $$$b_1,b_2,\ldots,b_n$$$, along with a binary string $$$c_1c_2\ldots c_n$$$ of length $$$n$$$.

There is also an integer $$$x$$$ which is initialized to $$$0$$$.

The game consists of $$$n$$$ rounds. For $$$i = 1,2,\ldots,n$$$, the round proceeds as follows:

If $$$c_i = \mathtt{0}$$$, Gellyfish will be the active player. Otherwise, if $$$c_i = \mathtt{1}$$$, Flower will be the active player.
The active player will perform exactly one of the following operations:
- Set $$$x:=x \oplus a_i$$$.
- Set $$$x:=x \oplus b_i$$$.

Here, $$$\oplus$$$ denotes the bitwise XOR operation.

Gellyfish wants to minimize the final value of $$$ x $$$ after $$$ n $$$ rounds, while Flower wants to maximize it.

Find the final value of $$$ x $$$ after all $$$ n $$$ rounds if both players play optimally.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the number of rounds of the game.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \lt 2^{60}$$$).

The third line of each test case contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \leq b_i \lt 2^{60}$$$).

The fourth line of each test case contains a binary string $$$c$$$ of length $$$n$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test case, output a single integer — the final value of $$$ x $$$ after all $$$ n $$$ rounds.

Note

In the first test case, there's only one round and Gellyfish is the active player of that round. Therefore, she will choose $$$a_1$$$, and the final value of $$$x$$$ is $$$0$$$.

In the second test case, Flower will be the active player in both rounds. She will choose $$$a_1$$$ and $$$b_2$$$, and the final value of $$$x$$$ is $$$a_1 \oplus b_2 = 15$$$. Flower may also choose $$$b_1$$$ and $$$a_2$$$ instead for the same result of $$$x=a_2 \oplus b_1 = 15$$$.

In the third test case, $$$a_1 = b_1$$$ so it doesn't matter what decision Gellyfish makes in the first round. In the second round:

If Flower chooses $$$a_2$$$, then $$$x$$$ will become $$$7$$$. Gellyfish will choose $$$b_3$$$ in the third round, so the final value of $$$x$$$ will be $$$4$$$.
Otherwise, Flower chooses $$$b_2$$$, then $$$x$$$ will become $$$4$$$. Gellyfish will choose $$$a_3$$$ in the third round, so the final value of $$$x$$$ will be $$$6$$$.

Flower wants to maximize the final value of $$$x$$$, so Flower will choose $$$b_2$$$ in the second round. Therefore, the final value of $$$x$$$ will be $$$6$$$.

Gellyfish and Forget-Me-Not

Examples