B. Yugandhar's Letter for Diya
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Yugandhar likes Diya, so he wants to tell his feelings by writing it on letter.

For simplicity letter is a $$$2D$$$ grid of $$$n$$$ rows and $$$m$$$ columns. Initially,all cells are white except for a blue cell $$$(x,y)$$$. Diya likes pink color, so Yugandhar started to put $$$k$$$ pink drops on $$$k$$$ different cells which are white.

After that,the following two events occur alternately in order,until every cell become either blue or pink.

  1. Cells adjacent to all blue cells which are white becomes blue.
  2. Cells adjacent to all pink cells which are white become pink.

Help Yugandhar by telling him what the maximum pink cells he will get if he choose $$$k$$$ cells optimally.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10$$$). The description of the test cases follows.

The first line of each testcase contains two integers $$$n,m$$$ ($$$1 \le n,m \le 10^9$$$), the dimensions of letter.

The second line of each testcase contains three integers $$$x,y,k$$$ ($$$1 \le x \le n$$$, $$$1 \le y \le m$$$, $$$0 \le k \le nm-1$$$), the coordinates of blue drop and number of cells he have to put pink drops.

Output

For each test case, print a single integer — the maximum pink cells he will get if he choose $$$k$$$ cells optimally.

Example
Input
4
1 1
1 1 0
2 2
1 2 1
2 3
2 1 5
4 5
3 4 2
Output
0
2
5
16
Note

In the first test case,you can't get any pink cell.

In the second test case, initially $$$(1,2)$$$ is blue.

The optimal selection for $$$k=1$$$ is $$$(2,2)$$$.After choosing $$$(2,2)$$$ the following happens:

  1. $$$(1,1)$$$ becomes blue;
  2. $$$(2,1)$$$ becomes pink.

The maximum pink cells we obtained is $$$2$$$ which are $$$(2,1)$$$ and $$$(2,2)$$$.