Prof. Pang Earning Aus

Prof. Pang has only $1$ Au in his pocket. (Yes, Prof. Pang is from Austan, and he uses the currency Au there.)

He makes money using a balloon store and a candy store. In the balloon store, Prof. Pang can pay $1$ Au to buy $k\_{ab}$ balloons, or pay $1$ candy to buy $k\_{cb}$ balloons. In the candy store, he can pay $1$ Au to buy $k\_{ac}$ candies, or pay $1$ balloon to buy $k\_{bc}$ candies. He can also sell one balloon for $k\_{ba}$ Au and sell one candy for $k\_{ca}$ Au. The balloon store has $n\_b$ balloons, and the candy store has $n\_c$ candies. He can buy only as many items as the stores have. Selling items does not increase the number of balloons or candies in the stores.

Each of the six transactions can be performed in any order, any number of times ($0$ or more). The transactions cannot be split. For example, he cannot pay $1/2$ Au to buy $k\_{ab}/2$ balloons.

Find the maximum number of Au he can make.

The first line contains a single integer $T$ ($1\le T\le 1000$), the number of test cases.

Each of the next $T$ lines contains eight integers $n\_b$, $n\_c$, $k\_{ab}$, $k\_{ba}$, $k\_{ac}$, $k\_{ca}$, $k\_{bc}$, $k\_{cb}$ ($1\le n\_b, n\_c\le 10^9$, $1\le k\_{ab}, k\_{ba}, k\_{ac}, k\_{ca}, k\_{bc}, k\_{cb}\le 100$), separated by single spaces.

For each test case, print one line containing the maximum number of Au.

In the first example, Prof. Pang buys $2$ balloons with $1$ Au and then sells $2$ balloons for $4$ Au. Then he buys $2$ candies with $1$ Au and sells $2$ candies for $4$ Au.