Description

Given two numbers $x$ and $y$, you can perform the following two operations on $x$ any number of times:

Pay a cost of $c$ to assign $x \leftarrow x \operatorname{AND} a$.

Pay a cost of $d$ to assign $x \leftarrow x \operatorname{OR} b$.

Where $\operatorname{AND}$ and $\operatorname{OR}$ represent bitwise AND and bitwise OR operations respectively.

You need to determine the minimum cost to transform $x$ into $y$. If it is impossible, output $-1$.

Help: What are bitwise AND and bitwise OR?

Input Format

This problem contains multiple test cases.

The first line of input contains an integer $T$, representing the number of test cases.

For each test case, there is one line containing six integers $x, y, a, b, c, d$, as described in the problem statement.

Output Format

For each test case, output one integer representing the answer.

5
1 15 2 14 3 5
1 3 3 14 9592 382
0 5 2 5 3492 12
194928 90283 59980 344444 182 959304
767894141 142877299 413934195 252884611 340885 421240

5
9974
12
-1
762125

Hint

Sample Explanation

• For the first test case, you can spend a cost of $5$ to perform a bitwise OR with $14$, obtaining $15$, which meets the requirement. It can be proven that no better solution exists.

• For the second test case, you can first spend $382$ to perform a bitwise OR with $14$, obtaining $15$, then spend $9592$ to perform a bitwise AND with $3$, obtaining $3$, which meets the requirement. The total cost is $9974$.

• For the fourth test case, it can be proven that no solution exists.

Data Constraints

Subtasks are used in this problem.

• Subtask 0 (0 pts): Sample cases.
• Subtask 1 (10 pts): $x, y, a, b < 2^3$.
• Subtask 2 (10 pts): $y = 2^k - 1$, where $k$ is a non-negative integer.
• Subtask 3 (30 pts): $x, y, a, b < 2^{10}$.
• Subtask 4 (20 pts): $c = d = 1$.
• Subtask 5 (30 pts): $x, y, a, b < 2^{30}$.

For all test cases, it is guaranteed that $1 \le T \le 10^5$, $0 \le x, y, a, b, c, d < 2^{30}$.