1409_B. 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.
```python
for _ in range(int(input())):
  a,b,x,y,n=map(int,input().split())
  
  if n>=((a-x)+(b-y)):
    print(x*y)
  else:
    if a>=b and n<=(b-y):
      print(a*(b-n))
    elif b>a and n<=(a-x):
      print((a-n)*b)
    elif n<=(a-x) and n<=(b-y):
      print(min((a-n)*b,a*(b-n)))
    else:
      
      if n>(a-x):
        qq=x*(b-(n-(a-x)))
      else:
        qq=(a-n)*b
   
      if n>(b-y):
        qq2=(a-(n-(b-y)))*y
      else:
        qq2=a*(b-n)
      #print(qq,qq2,"pp")
      print(min(qq,qq2))

```