# Luffy Will Become the Pirate King Edgedancer CUET CSE Fest 2022 - Inte...
Limits 1s, 512 MB

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

InputOutput
2
3
1 3 5
4 3 1
10 5 8
2
1 2
1 2
2 1

23
4


### Submit 