Luffy Will Become the Pirate King

Whitebeard is testing Luffy to see if he can become the Pirate King. Whitebeard has given Luffy three arrays $a, b, c$ of length $n$ and an integer $x$. Initially $x = 1$. Luffy initially has score of $0$ and can perform the following operation at most $n$ time:

• Select $1\leq i \leq n$ such that $i$ has not been selected in previous operations and update $x$ by multiplying it with $a_i$ that is assign $x = x \times a_i$. If the updated $x$ is even then add $b_i$ to the score or if updated $x$ is odd then add $c_i$ to the score.

Luffy wants to maximize his score. So, he is asking for your help. Help Luffy become the pirate king.

Input

The input consists of multiple test cases. The first line contains a single integer $T(1 \leq T \leq 4 \times 10{^4})$ — the number of test cases.

Each test case starts with $n (1\leq n \leq 2 \times 10^{5})$ and then three lines follow.

The second line of the test case contains $n$ integers $a_i (1 \leq a_i \leq 10^6)$.

Third line of the test case contains $n$ integers $b_i (-10^9 \leq b_i \leq 10^9)$.

Fourth line of the test case contains $n$ integers $c_i (-10^9 \leq c_i \leq 10^9)$.

Sum of $n$ of all test cases does not exceed $2 \times 10^{5}$.

Output

For each test case, output the maximum score Luffy can obtain if he performs the operations optimally.

Sample

Input	Output
2 3 1 3 5 4 3 1 10 5 8 2 1 2 1 2 2 1	23 4