G. Pack
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You have $$$n$$$ items of type A and $$$m$$$ items of type B. Each A item has a value of $$$a$$$ and each B item has a value of $$$b$$$.

You now need to determine a packaging solution for a certain product, which includes a certain number of item A and a certain number of item B (it is allowed to contain only item A or only item B), satisfying the total value of the items to be $$$k$$$. In this packaging solution, you aim to package as many products as possible until the remaining A and B items are not sufficient to form a complete product.

Your task is to find the minimum number of items that remain unpackaged among all possible packaging solutions.

Input

There are multiple test cases. The first line inputs an integer $$$T$$$ ($$$1 \le T \le 50$$$) indicating the number of test case groups. For each test case:

The first line contains five positive integers $$$n, m, a, b, k$$$ ($$$1 \le n, m \le 10^9, 1 \le a, b \le 10^9, 1 \le k \le 10^9$$$).

Output

For each test case, output a single integer on a new line, representing the minimum number of items that cannot be packaged.

Example
Input
8
10 8 2 3 12
3 3 2 2 8
1 3 2 2 10
6 6 3 5 16
341 329 5 6 741
727 521 18 9 576
290646493 622766369 133 76 578504001
285261289 308082376 109 3 922747797
Output
3
2
4
0
122
48
2764422
5914615
Note

In the first test case, there are $$$10$$$ objects of type A with a value of $$$2$$$ and $$$8$$$ objects of type B with a value of $$$3$$$. They can be packaged into products with a composition of $$$3$$$ A objects and $$$2$$$ B objects. This way, they can be packaged into $$$3$$$ products, leaving $$$1$$$ A object and $$$2$$$ B objects remaining.

In the second test case, there are $$$3$$$ objects of type A with a value of $$$2$$$ and $$$3$$$ objects of type B with a value of $$$2$$$. They can be packaged into products with a composition of $$$2$$$ A objects and $$$2$$$ B objects. This way, they can be packaged into $$$1$$$ product, leaving $$$1$$$ A object and $$$1$$$ B object remaining.