Minimum Hours to Produce Parts

You are given two types of machines. There are (n) type A machines, each producing (x) parts per hour, and (m) type B machines, each producing (y) parts per hour. Together, these machines produce parts concurrently. Your task is to compute the minimum number of hours required to produce at least (k) parts. Mathematically, the hours needed can be represented as:

[ \text{hours} = \lceil \frac{k}{n \times x + m \times y} \rceil ]

Note that if the total production in one hour does not exactly divide (k), you will need to round up to the next whole hour. There are multiple test cases to process.

inputFormat

The first line of input contains a single integer (t) ((1 \leq t \leq 10^4)) indicating the number of test cases. Each of the following (t) lines contains five space-separated integers: (n), (m), (x), (y), and (k), where (n) and (m) denote the number of type A and type B machines respectively, (x) and (y) denote their production outputs per hour, and (k) is the target number of parts.

outputFormat

For each test case, output a single integer on a new line — the minimum number of hours required to produce at least (k) parts.## sample

3
3 2 5 4 100
1 1 10 10 50
10 5 2 3 60

5
3
2