402822: GYM100889 F Flipping Rectangles

You are given 2 coordinate axis aligned rectangles R₁ and R₂. You can apply at most K moves on R₁.

A move is defined as follows: You can choose any of the four edges E of the current configuration of R₁ and flip(reflect) R₁ about E. E can be different in each move. For example, if R₁ is currently between denoted by bottom-left and top-right corners by (0, 0) and (1, 1) and we flip it about the right edge(i.e. edge between (1, 1) and (1, 0)) then the configuration of R₁ will be between (1, 0) and (2, 1).

Let A be the area of overlap of R₂ and final configuration of R₁. What is the maximum overlap area you can achieve?

The first line contains T(1 ≤ T ≤ 10⁵), the number of test cases. Every test cases has three lines of input. First line has four integers S_x, S_y, S_w, S_h, where (S_x, S_y) are the x and y coordinates of the bottom-left corner of the R₁ rectangle. S_w is its width (along x-axis) and S_h is its height(along y-axis). Next line has four integers D_x, D_y, D_w, D_h representing the R₂ rectangle in a similar fashion. Next line has one integer K(0 ≤ K ≤ 10⁹). Absolute value of all coordinates doesn't exceed 10⁹. Width and height lie between 1 and 10⁹(both inclusive).

Output for each query, the maximum overlap area you can achieve.

1
0 0 10 10
20 20 5 10
0

0

Sample test case 1:

There is no overlap initially and we can't make any move.