Minimum Product

You are given four integers a, b, x and y. Initially, a ≥ x and b ≥ y. You can do the following operation no more than n times:

• Choose either a or b and decrease it by one. However, as a result of this operation, value of a cannot become less than x, and value of b cannot become less than y.

Your task is to find the minimum possible product of a and b (a ⋅ b) you can achieve by applying the given operation no more than n times.

You have to answer t independent test cases.

Input

The first line of the input contains one integer t (1 ≤ t ≤ 2 ⋅ 10^4) — the number of test cases. Then t test cases follow.

The only line of the test case contains five integers a, b, x, y and n (1 ≤ a, b, x, y, n ≤ 10^9). Additional constraint on the input: a ≥ x and b ≥ y always holds.

Output

For each test case, print one integer: the minimum possible product of a and b (a ⋅ b) you can achieve by applying the given operation no more than n times.

Example

Input

7 10 10 8 5 3 12 8 8 7 2 12343 43 4543 39 123212 1000000000 1000000000 1 1 1 1000000000 1000000000 1 1 1000000000 10 11 2 1 5 10 11 9 1 10

Output

70 77 177177 999999999000000000 999999999 55 10

Note

In the first test case of the example, you need to decrease b three times and obtain 10 ⋅ 7 = 70.

In the second test case of the example, you need to decrease a one time, b one time and obtain 11 ⋅ 7 = 77.

In the sixth test case of the example, you need to decrease a five times and obtain 5 ⋅ 11 = 55.

In the seventh test case of the example, you need to decrease b ten times and obtain 10 ⋅ 1 = 10.

inputFormat

Input

The first line of the input contains one integer t (1 ≤ t ≤ 2 ⋅ 10^4) — the number of test cases. Then t test cases follow.

The only line of the test case contains five integers a, b, x, y and n (1 ≤ a, b, x, y, n ≤ 10^9). Additional constraint on the input: a ≥ x and b ≥ y always holds.

outputFormat

Output

For each test case, print one integer: the minimum possible product of a and b (a ⋅ b) you can achieve by applying the given operation no more than n times.

Example

Input

7 10 10 8 5 3 12 8 8 7 2 12343 43 4543 39 123212 1000000000 1000000000 1 1 1 1000000000 1000000000 1 1 1000000000 10 11 2 1 5 10 11 9 1 10

Output

70 77 177177 999999999000000000 999999999 55 10

Note

In the first test case of the example, you need to decrease b three times and obtain 10 ⋅ 7 = 70.

In the second test case of the example, you need to decrease a one time, b one time and obtain 11 ⋅ 7 = 77.

In the sixth test case of the example, you need to decrease a five times and obtain 5 ⋅ 11 = 55.

In the seventh test case of the example, you need to decrease b ten times and obtain 10 ⋅ 1 = 10.

样例

7
10 10 8 5 3
12 8 8 7 2
12343 43 4543 39 123212
1000000000 1000000000 1 1 1
1000000000 1000000000 1 1 1000000000
10 11 2 1 5
10 11 9 1 10

70
77
177177
999999999000000000
999999999
55
10

</p>