Prof. Pang의 Au 벌기

Prof. Pang은 주머니에 1 Au만 가지고 있다. (그렇다. Prof. Pang은 Austan 출신이라 그곳의 화폐인 Au를 쓴다.)

그는 풍선 가게와 사탕 가게를 이용해 돈을 번다. 풍선 가게에서는 1 Au를 내고 풍선 $k\_{ab}$개를 살 수 있고, 사탕 1개를 내고 풍선 $k\_{cb}$개를 살 수 있다. 사탕 가게에서는 1 Au를 내고 사탕 $k\_{ac}$개를 살 수 있고, 풍선 1개를 내고 사탕 $k\_{bc}$개를 살 수 있다. 풍선 1개를 팔면 $k\_{ba}$ Au를 받고, 사탕 1개를 팔면 $k\_{ca}$ Au를 받는다. 풍선 가게에는 풍선이 $n\_b$개, 사탕 가게에는 사탕이 $n\_c$개 있다. 가게에 남은 수량 안에서만 살 수 있다. 물건을 팔아도 가게의 풍선과 사탕 수는 늘지 않는다.

여섯 가지 거래는 어떤 순서로든, 몇 번이든($0$번 이상) 할 수 있다. 다만 거래를 나눌 수는 없다. 예를 들어 1/2 Au를 내고 풍선 $k\_{ab}/2$개를 살 수는 없다.

그가 벌 수 있는 Au의 최대값을 구하라.

첫 줄에 테스트 케이스의 개수 $T$ ($1\le T\le 1000$)가 주어진다.

이어지는 $T$개 줄에는 각각 여덟 개의 정수 $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$)가 공백 하나로 구분되어 주어진다.

각 테스트 케이스마다 Au의 최대값을 한 줄에 출력한다.

첫 번째 예제에서 Prof. Pang은 1 Au로 풍선 2개를 사고, 풍선 2개를 팔아 4 Au를 받는다. 그다음 1 Au로 사탕 2개를 사고, 사탕 2개를 팔아 4 Au를 받는다.