Description

You are the captain of the school programming competition team, leading your classmates to Chongqing to participate in the CCPC. According to the team's tradition, as the captain, you need to treat your classmates to a meal, and you plan to eat the local specialty hot pot.

According to statistics, there are $x$ students in the team who only accept spicy food, $y$ students who only accept non-spicy food, and $z$ students who accept both spicy and non-spicy food. The hot pot restaurant you visit offers three types of pots:

• Spicy pot, which can serve at most two students who accept spicy food, costing $a$ yuan per serving.
• Mixed pot, which can serve at most one student who accepts spicy food and at most one student who accepts non-spicy food, costing $b$ yuan per serving.
• Non-spicy pot, which can serve at most two students who accept non-spicy food, costing $c$ yuan per serving.

You want to know the minimum amount of money needed to ensure that all students can eat hot pot according to their preferences.

Input

There are multiple test cases in a single test file. The first line of the input contains a single integer $T$ ($1 \le T \le 2025$), indicating the number of test cases.

For each test case:

• Each line contains $6$ positive integers $x, y, z, a, b, c$ ($1 \le x, y, z, a, b, c \le 2025$), representing the number of students in each category and the prices of the three types of hot pots.

Output

For each test case, output a single integer on a single line, representing the minimum possible cost to ensure that all students can eat hot pot according to their preferences.

Example

Sample Input 1

6
3 1 4 1 5 9
1 1 4 5 1 4
1 5 2 8 2 3
9 6 2 3 5 10
1 5 8 2 8 7
1 9 5 10 3 5

Sample Output 1

8
3
9
39
29
26

Note

• In the first example, you can let all mixed preference students eat spicy food, then order three spicy pots and one mixed pot, with a total cost of $1 \times 3 + 5 \times 1 = 8$.
• In the second example, you can let the mixed preference students have two eat spicy and two eat non-spicy, then order three mixed pots, with a total cost of $1 \times 3 = 3$.