Canadian Computing Competition: 2026 Stage 1, Senior #5

You recently inherited a beautiful plot of land, which can be viewed as a grid with ~N~ rows and ~M~ columns. Now you want to protect your land from trespassers by building a giant fence on it. You will build this fence by choosing up to ~K~ grid cells and filling each of them with a concrete block; these cells are on the fence. Due to mysterious construction laws, the cell in row ~R~ and column ~C~ must be on the fence. Also, the fence cells must form a single connected component—you should be able to get between any two cells on the fence by moving vertically or horizontally (not diagonally) through fence cells only.

The cells in row 1, column 1, row ~N~, and column ~M~ are called edge cells. A cell not on the fence is outside the fence if you can get from that cell to an edge cell by moving vertically, horizontally, or diagonally, without going through any fence cells. Otherwise, the cell is inside the fence. The figure below shows some examples of valid and invalid fences.

This is a valid fence made of 17 blocks, with 5 inside cells.

This fence is invalid because it is not connected.

This fence is valid, but it encloses zero inside cells.

You want to protect as much of your land as possible. Find the largest number of inside cells you can enclose within your fence.

Input Specification

The first line of input contains an integer ~T~, the number of test cases in the input.

The next ~T~ lines each contain a test case, consisting of five space-separated integers: ~N~, ~M~, ~K~, ~R~, and ~C~ (~1 \le K \le NM~, ~1 \le R \le N~, ~1 \le C \le M~).

The table on the next page shows how the available 15 marks are distributed.

Marks Awarded	Bounds on ~T~	Bounds on ~N,M~	Additional Constraints
1 mark	~T \le 1000~	~1 \le N,M \le 10^9~	~K=NM~
2 marks	~T \le 10~	~1 \le N,M \le 6~	None
2 marks	~T \le 10~	~1 \le N,M \le 40~	None
2 marks	~T \le 10~	~1 \le N,M \le 300~	None
2 marks	~T \le 10~	~1 \le N,M \le 2\,000~	None
3 marks	~T \le 10~	~1 \le N,M \le 10^6~	None
3 marks	~T \le 1000~	~1 \le N,M \le 10^9~	None

Output Specification

Output ~T~ lines. The ~t~-th line should contain a single integer, the answer to test case ~t~.

Sample Input

2
5 6 12 3 4
3 6 18 2 4

Output for Sample Input

4
3

Explanation for Sample Output

Below is an optimal fence for the first test case:

Below is an optimal fence for the second test case: