Aman, Gitanshu and Vishal have recently been selected as admins of DCE Coders. Kapish is pretty happy with the selection, but he wants to make sure that the new admins understand the importance of team-work if they are to take DCE Coders forward in the coming year. Keeping this in mind, he challenges the 3 of them to a game.

Kapish takes all 3 of them to a long narrow corridor, and gives each of them separate start and end coordinates. The task is simple: All of them have to go from their start coordinates to their respective end coordinates simultaneously (i.e. using the same number of moves). However, they can only move in some discrete steps, which are also given by Kapish. He provides one array (of size ‘N’) of acceptable jumps to each of the 3. The challenge is that in one move, all 3 of them have to agree upon 1 common index (from 0 to N-1) and then they would add the value corresponding to that index from their respective arrays to get their new coordinates.

Now Pushap, who likes challenges (such as jumping off moving trains!!), further complicates the problem. If the index selected in the previous move is odd, then it must be even for the current move, and vice versa. They can choose any index for the first move.

The 3 new admins are required to find the minimum number of moves in which all 3 of them can simultaneously reach their destinations. Can you help them?

Note 1: You can assume the corridor is 1 dimensional and infinite.

Note 2: It is possible for more than 1 person to be on the same coordinate at the same time.

Input

First line of input contains T the number of test cases.

First line of each test case contains 3 space-separated integers, A1, G1 and V1, the initial coordinates for the 3.

Next line contains 3 space separated integers, A2, G2 and V2, the final coordinates for the 3.

Next line contains a single integer, N.

Next 3 lines contain N space-separated integers each, denoting arrays A, G and V of acceptable jumps for the 3.

Output

Output a single integer (in a separate line) per test case, containing the minimum number of moves.

If it is not possible for them to reach their destinations simultaneously, output -1.

Example

Input:
1
1 2 3
2 3 5
2
1 3
1 2
2 1

Output:
1

Explanation

The 3 of them can choose index 0 in the first move to reach their destinations.

Constraints

1 ≤ T ≤ 5

-50 ≤ A1, A2, G1, G2, V1, V2 ≤ 50

1 ≤ N ≤ 20

-10 ≤ A[i], G[i], V[i] ≤ 10