Background

You may play the game Starcraft I first before you do this problem ^_^.

Description

Suppose you are using Protoss. At the beginning of the game, you have n probes, a nexus and almost unlimited number of pylons. You can build a probe in the nexus per 3 Starcraft time units(STs), and this will cost you z units of minerals. A probe can gather x units of minerals or y units of gas per ST. What's the minimum time to get A units of minerals and B units of gas, if you build probes at nexus only and don't build any buildings?

Assume that in the current map there are almost unlimited mineral fields and unlimited vespene geysers, and on each vespene geyser, a Protoss Assimilator has been built successfully.

Input

Multiple test cases, the number of them is given in the very first line.

Each test case contains one line with 6 positive integers n, x, y, z, A, B separated by one space. All numbers in the input file will be less than 21.

Output

For each test case, output one line, which contains a single integer, the minimum time in ST.

Example

Input:
1
1 2 3 4 5 6
Output:
5