Admission Fee

Aiz Onsen has a bathhouse and a pool. To use the bathhouse, you need to buy a bathing ticket, and to use the pool, you need to buy a pool ticket. Prices for these tickets may vary from day to day. In addition, Aiz Onsen has the following rules.

• Tickets are valid only once on the day of purchase.
• If you buy 5 or more bathing tickets and 2 or more pool tickets at once, you will get a 20% discount on all tickets.

Sadayoshi, who loves hot springs, and his friends go to Aiz Onsen almost every day. They are all capricious and use different numbers from day to day. Aiz Onsen has discount rules, so if you work together as a group and buy well, you may be able to reduce the total price.

Create a program that outputs the cheapest total price when the bathing ticket and pool ticket charges, the number of bathing tickets to be used and the number of pool tickets are given as inputs. However, if buying more tickets than you use will reduce the total price, you do not have to use all the tickets you bought.

input

The input is given in the following format.

N x1 y1 b1 p1 x2 y2 b2 p2 :: xN yN bN pN

N (1 ≤ N ≤ 365) on the first line is the number of days for which you want to calculate the charge. In the next N lines, the bathing ticket fee xi (100 ≤ xi ≤ 1000) for the i-day day, the pool ticket fee yi (100 ≤ yi ≤ 1000), the number of bathing tickets used bi (0 ≤ bi ≤ 6), The number of pool tickets to use pi (0 ≤ pi ≤ 6) is given. Both bathing tickets and pool tickets are charged in increments of 50 yen.

output

Print the cheapest total price on one line for each day.

Example

Input

2 100 100 1 1 1000 500 5 2

Output

200 4800

inputFormat

outputFormat

outputs the cheapest total price when the bathing ticket and pool ticket charges, the number of bathing tickets to be used and the number of pool tickets are given as inputs. However, if buying more tickets than you use will reduce the total price, you do not have to use all the tickets you bought.

input

The input is given in the following format.

N x1 y1 b1 p1 x2 y2 b2 p2 :: xN yN bN pN

N (1 ≤ N ≤ 365) on the first line is the number of days for which you want to calculate the charge. In the next N lines, the bathing ticket fee xi (100 ≤ xi ≤ 1000) for the i-day day, the pool ticket fee yi (100 ≤ yi ≤ 1000), the number of bathing tickets used bi (0 ≤ bi ≤ 6), The number of pool tickets to use pi (0 ≤ pi ≤ 6) is given. Both bathing tickets and pool tickets are charged in increments of 50 yen.

output

Print the cheapest total price on one line for each day.

Example

Input

2 100 100 1 1 1000 500 5 2

Output

200 4800

样例

2
100 100 1 1
1000 500 5 2

200
4800

</p>