Penny started studying in a community college. However she did not tell Leonard about this because she did not want Leonard helping her at every point in her studies. This went well until the professor ordered her to perform an advanced experiment. In this experiment she was given an advanced microbiological specimen. This specimen is placed in an n × m size grid which is divided into 1 × 1 cells.

It expands according to following rules.

If at time t, the specimen occupies (x, y), then at time t + 1 it can expand to at most any two cells out of (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1).

For example if at t = 0 sec if the specimen occupies (4, 5), then at time t = 1 sec, the state of the grid can be any of the following:

1. specimen at (4, 5), (5, 5) and (3, 5).
2. specimen at (4, 5), (5, 5) and (4, 6).
3. specimen at (4, 5), (5, 5) and (3, 4).
4. specimen at (4, 5), (3, 5) and (4, 6).
5. specimen at (4, 5), (3, 5) and (4, 4).
6. specimen at (4, 5), (4, 6) and (4, 4).

Note - At t = 2 sec, it can expand from all the points that the specimen occupied at t = 1.

The professor asks penny to find the minimum time it takes for the specimen to fill the entire grid.

Since penny is not so smart at math and she can't ask Leonard to help her, she turns to you for help and to find the solution to above problem.

Input

T - The number of test cases.

n m - number of row and columns in the grid.

x y - coordinate of the initial position of the specimen.

Output

The minimum time in seconds it takes for specimen to fill in the entire grid.

Constraints

1 <= T <= 50

1 <= n, m <= 500

1 <= x <= n

1 <= y <= m

Example

Input:
2
1 1
1 1
10 10
6 4

Output:
0
11