You are given four integers $a$, $b$, $x$ and $y$. Initially, $a \ge x$ and $b \ge 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 \cdot 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 \le t \le 2 \cdot 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 \le a, b, x, y, n \le 10^9$). Additional constraint on the input: $a \ge x$ and $b \ge y$ always holds.


-----Output-----

For each test case, print one integer: the minimum possible product of $a$ and $b$ ($a \cdot 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 \cdot 7 = 70$.

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

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

In the seventh test case of the example, you need to decrease $b$ ten times and obtain $10 \cdot 1 = 10$.
[{"code": "t = int(input())\n# a = list(map(int, input().split()))\nfor _ in range(t):\n    a,b,x,y,n = map(int,input().split())\n    \n    options = []\n    a2 = max(a-n,x)\n    b2 = max(b-(n-(a-a2)),y)\n    options.append(a2*b2)\n    \n    b2 = max(b-n,y)\n    a2 = max(a-(n-(b-b2)),x)\n    options.append(a2*b2)\n    \n    print(min(options))", "passed": true, "time": 0.76, "memory": 14268.0, "status": "done"}, {"code": "for i in range(int(input())):\n\ta, b, x, y, n = list(map(int, input().split()))\n\n\ta1, b1, x1, y1, n1 = a, b, x, y, n\n\ttoRemove = min(a1-x1, n1)\n\tn1 -= toRemove\n\ta1 -= toRemove\n\ttoRemove = min(n1, b1-y1)\n\tn1 -= toRemove\n\tb1 -= toRemove\n\tans1 = a1*b1\n\n\ta1, b1, x1, y1, n1 = a, b, x, y, n\n\ttoRemove = min(b1-y1, n1)\n\tn1 -= toRemove\n\tb1 -= toRemove\n\ttoRemove = min(n1, a1-x1)\n\tn1 -= toRemove\n\ta1 -= toRemove\n\tans2 = a1*b1\n\n\tprint(min(ans1, ans2))\n\n", "passed": true, "time": 0.24, "memory": 14276.0, "status": "done"}, {"code": "def solve(a, b, x, y, n):\n    x = a-x\n    y = b-y\n    m = min(x, n)\n    n -= m\n    a -= m\n    m = min(y, n)\n    b -= m\n    return a*b\n    \nfor _ in range(int(input())):\n    a, b, x, y, n = list(map(int, input().split()))\n    print(min(solve(a, b, x, y, n), solve(b, a, y, x, n)))\n", "passed": true, "time": 0.14, "memory": 14240.0, "status": "done"}, {"code": "t = int(input())\nfor i in range(t):\n    a, b, x, y, n = [int(i) for i in input().split()]\n    ans = a * b\n\n    ck = min(a - x, n)\n    ca = a - ck\n    cn = n - ck\n    cb = b - min(b - y, cn)\n    ans = min(ans, ca * cb)\n\n    ck = min(b - y, n)\n    cb = b - ck\n    cn = n - ck\n    ca = a - min(a - x, cn)\n    ans = min(ans, ca * cb)\n\n    print(ans)\n", "passed": true, "time": 0.14, "memory": 14352.0, "status": "done"}, {"code": "for _ in range(int(input())):\n    a, b, x, y, n = list(map(int, input().split()))\n    posa = max(a - n, x)\n    posb = max(b - n, y)\n    if posa < posb:\n        n -= a - posa\n        a = posa\n        b = max(b - n, y)\n    else:\n        n -= b - posb\n        b = posb\n        a = max(a - n, x)\n    print(a * b)\n", "passed": true, "time": 0.23, "memory": 14244.0, "status": "done"}, {"code": "\"\"\"T=int(input())\nfor _ in range(0,T):\n    n=int(input())\n    a,b=map(int,input().split())\n    s=input()\n    s=[int(x) for x in input().split()]\n    for i in range(0,len(s)):\n        a,b=map(int,input().split())\"\"\"\n\n\nT=int(input())\nfor _ in range(0,T):\n    a,b,x,y,n=list(map(int,input().split()))\n\n    A=a\n    B=b\n    N=n\n\n    d1 = (a-x)\n    d2 = (b-y)\n\n    t1=min(d1,n)\n    a-=t1\n    n-=t1\n    t2=min(d2,n)\n    b-=t2\n    n-=t2\n    #print(a,b)\n    ans=(a*b)\n\n    d1 = (A-x)\n    d2 = (B-y)\n\n    t2=min(d2,N)\n    B-=t2\n    N-=t2\n    t1=min(d1,N)\n    A-=t1\n    N-=t1\n\n    \n    #print(A,B)\n    ans=min(ans,A*B)\n    print(ans)\n\n\n    \n    \n", "passed": true, "time": 0.23, "memory": 14124.0, "status": "done"}, {"code": "import sys\n\n\ndef read_int():\n    return int(sys.stdin.readline())\n\n\ndef read_ints():\n    return list(map(int, sys.stdin.readline().split(' ')))\n\n\nt = read_int()\nfor case_num in range(t):\n    a, b, x, y, n = read_ints()\n    n1 = min(n, a - x)\n    ans = (a - n1) * (b - min(n - n1, b - y))\n    n2 = min(n, b - y)\n    ans = min(ans, (b - n2) * (a - min(n - n2, a - x)))\n    print(ans)\n", "passed": true, "time": 0.23, "memory": 14112.0, "status": "done"}, {"code": "import sys\ninput=sys.stdin.readline\n\n\ndef fmin(a,b,x,y,n):\n    v=max(a-n,x)\n    val=n-(a-v)\n    v1=max(b-val,y)\n    return v*v1\n\nT=int(input())\nfor _ in range(T):\n    a,b,x,y,n=list(map(int,input().split()))\n    v=min(fmin(a,b,x,y,n),fmin(b,a,y,x,n))\n    print(v)\n", "passed": true, "time": 0.15, "memory": 14132.0, "status": "done"}, {"code": "for i in range(int(input())):\n\ta, b, x, y, n = (int(j) for j in input().split())\n\tans = 10 ** 18\n\n\td1 = a - x\n\td2 = b - y\n\tif (d1 > n):\n\t\tans = min(ans, (a - n) * b)\n\telif (d1 + d2 > n):\n\t\tans = min(ans, x * (b - n + d1))\n\telse:\n\t\tans = min(ans, x * y)\n\n\tx, y = y, x\n\ta, b = b, a\n\n\td1 = a - x\n\td2 = b - y\n\tif (d1 > n):\n\t\tans = min(ans, (a - n) * b)\n\telif (d1 + d2 > n):\n\t\tans = min(ans, x * (b - n + d1))\n\telse:\n\t\tans = min(ans, x * y)\n\n\tprint(ans)", "passed": true, "time": 0.14, "memory": 14316.0, "status": "done"}, {"code": "t = int(input())\nfor _ in range(t):\n    a, b, x, y, n = map(int, input().split())\n    a1 = a - min(a - x, n)\n    n1 = n - min(a - x, n)\n    b1 = b - min(b - y, n1)\n    \n    b2 = b - min(b - y, n)\n    n2 = n - min(b - y, n)\n    a2 = a - min(a - x, n2)\n    print(min(a1 * b1, a2 * b2))", "passed": true, "time": 0.14, "memory": 14244.0, "status": "done"}, {"code": "import sys, math\nimport io, os\n#data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline\nfrom bisect import bisect_left as bl, bisect_right as br, insort\nfrom heapq import heapify, heappush, heappop\nfrom collections import defaultdict as dd, deque, Counter\n# from itertools import permutations,combinations\ndef data(): return sys.stdin.readline().strip()\ndef mdata(): return list(map(int, data().split()))\ndef outl(var): sys.stdout.write('\\n'.join(map(str, var)) + '\\n')\ndef out(var): sys.stdout.write(str(var) + '\\n')\nfrom decimal import Decimal\n# from fractions import Fraction\n# sys.setrecursionlimit(100000)\nmod = int(1e9) + 7\nINF=2**32\n\nfor t in range(int(data())):\n    a,b,x,y,n=mdata()\n    m1=max(a-n,x)\n    m2=max(b-n,y)\n    if m1<m2:\n        m2=max(b-(n-(a-m1)),y)\n    else:\n        m1=max(a-(n-(b-m2)),x)\n    out(m1*m2)", "passed": true, "time": 0.14, "memory": 14216.0, "status": "done"}, {"code": "# Fast IO (be careful about bytestring)\n\n# import os,io\n# input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline\n\n\nfor _ in range(int(input())):\n    a,b,x,y,n = list(map(int,input().split()))\n    if a + b - x - y < n:\n        print(x * y)\n    else:\n        minProduct = 10 ** 20\n        # Decreasing a first\n        if a - n >= x:\n            product = (a - n) * b\n            if product < minProduct:\n                minProduct = product\n        else:\n            product = x * max(y,b - n + a - x)\n            if product < minProduct:\n                minProduct = product\n        # Decreasing b first\n        if b - n >= y:\n            product = (b - n) * a\n            if product < minProduct:\n                minProduct = product\n        else:\n            product = y * max(x,a - n + b - y)\n            if product < minProduct:\n                minProduct = product\n        print(minProduct)\n", "passed": true, "time": 0.15, "memory": 14308.0, "status": "done"}, {"code": "for _ in range(int(input())):\n    a,b,x,y,n=list(map(int,input().split()))\n    c=max(a-n,x)\n    d=max(b-n,y)\n    if c<d:\n        ans=c\n        n-=a-c\n        d=max(b-n,y)\n        print(ans*d)\n    else:\n        ans=d\n        n-=b-d\n        c=max(a-n,x)\n        print(ans*c)\n\n", "passed": true, "time": 0.22, "memory": 14268.0, "status": "done"}, {"code": "def find(a,b,x,y,n):\n    req = a-x\n    min_val = min(req,n)\n    a -= min_val\n    n -= min_val\n    b -= n\n\n    return a*b\n\ndef solve(a,b,x,y,n,ans):\n    req1 = a-x\n    req2 = b-y\n    if req1+req2 <= n:\n        a = x\n        b = y\n        ans.append(str(a*b))\n    else:\n        min_val = find(a,b,x,y,n)\n        min_val = min(min_val,find(b,a,y,x,n))\n        ans.append(str(min_val))\n\ndef main():\n    t = int(input())\n    ans = []\n    for i in range(t):\n        a,b,x,y,n = list(map(int,input().split()))\n        solve(a,b,x,y,n,ans)\n\n    print('\\n'.join(ans))\n    \n\nmain()\n", "passed": true, "time": 0.14, "memory": 14172.0, "status": "done"}, {"code": "import sys, math, heapq, collections, itertools, bisect\nsys.setrecursionlimit(101000)\n\ndef solve(a, b, x, y, n):\n    diffa = a - x\n    diffb = b - y\n    first = min(diffb, n)\n    b -= first\n    n -= first\n    second = min(diffa, n)\n    a -= second\n    n -= second\n    return a*b\n\nt = int(input())\nfor _ in range(t):\n    # n = int(input())\n    a, b, x, y, n = map(int, input().split())\n    # a = list(map(int, input().split()))\n    print(min(solve(a, b, x, y, n), solve(b, a, y, x, n)))", "passed": true, "time": 0.14, "memory": 14380.0, "status": "done"}, {"code": "import sys\nimport math\ndef II():\n\treturn int(sys.stdin.readline())\n\ndef LI():\n\treturn list(map(int, sys.stdin.readline().split()))\n\ndef MI():\n\treturn list(map(int, sys.stdin.readline().split()))\n\ndef SI():\n\treturn sys.stdin.readline().strip()\nt = II()\nfor q in range(t):\n\ta,b,x,y,n = MI()\n\tif a-min(n,a-x)<b-min(n,b-y):\n\t\tb,a = a,b\n\t\ty,x = x,y\n\ttemp=min(n,b-y)\n\tn-=temp\n\tb-=temp\n\ta-=min(a-x,n)\n\tprint(a*b)\n\n\n\t\n", "passed": true, "time": 0.14, "memory": 14356.0, "status": "done"}, {"code": "t=int(input())\nfor _ in range(t):\n    a,b,x,y,n=map(int,input().split())\n    mina1 = max(x, a-n)\n    minb1 = max(y, b-(n-a+mina1))\n    minb2 = max(y, b-n)\n    mina2 = max(x, a-(n-b+minb2))\n    print(min(mina1*minb1,mina2*minb2))", "passed": true, "time": 0.14, "memory": 14156.0, "status": "done"}, {"code": "t = int(input())\nfor _ in range(t):\n    a, b, x, y, n = list(map(int, input().split()))\n    if max(a-n, x) > max(b-n, y):\n        a, b = b, a\n        x, y = y, x\n    d = a - x\n    a = max(a - n, x)\n    if a > x:\n        print(a * b)\n        continue\n    n -= d\n    b = max(b - n, y)\n    print(a * b)\n", "passed": true, "time": 0.14, "memory": 14100.0, "status": "done"}, {"code": "t=int(input())\nfor _ in range(t):\n    a,b,x,y,n=list(map(int,input().split()))\n    min_a=max(a-n,x)\n    min_b=max(b-n,y)\n    if min_a<min_b:\n        n = n - (a - min_a)\n        a=min_a\n\n        b=max(b-n,y)\n    else:\n        n = n - (b - min_b)\n        b = min_b\n\n        a = max(a - n, x)\n    print(a*b)", "passed": true, "time": 0.14, "memory": 14324.0, "status": "done"}, {"code": "from sys import stdin\n\ntt = int(stdin.readline())\n\nfor loop in range(tt):\n\n    a,b,x,y,n = map(int,stdin.readline().split())\n\n    ans = float(\"inf\")\n\n    if a-x + b-y < n:\n        print (x*y)\n        continue\n    \n    #first a\n    if a-x >= n:\n        ans = min(ans , (a-n) * b)\n    else:\n        rem = n - (a-x)\n        ans = min(ans , x * (b-rem))\n\n    #b\n    if b-y >= n:\n        ans = min(ans , (b-n) * a)\n    else:\n        rem = n - (b-y)\n        ans = min(ans , y * (a-rem))\n\n    print (ans)", "passed": true, "time": 0.14, "memory": 14288.0, "status": "done"}]