CRAN01 - An Experiment by Penny

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

Added by:CSI
Date:2013-02-16
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2017-07-24 22:15:07
nice logic...try with different cases on paper
2017-06-20 18:31:18
Nice Problem!!
2015-07-25 12:38:28
it should be (3,5) instead of (3,4) because it doesn't satisfying the above 4 movements..
code accepted with (3,5) instead of (3,4).
2015-04-06 05:24:04 Archangel
Nice problem :) easy but not very obvious logic..

Last edit: 2015-04-06 07:26:14
2014-10-31 17:27:30 Rajat (1307086)
awesome problem.Although had to take help.Heres a hint:
[removed]

[reply by cyclops: I've told you not to leave hints and spoilers in the comments section on several occasions. I sent you an email now.]

Last edit: 2014-10-31 18:09:41
2014-05-28 11:43:31 Vinay Sharma
took me a while to get the logic. So simple !!

Last edit: 2014-05-28 11:44:06
2014-02-02 06:39:30 Rishabh Sharma
I like dumb girls like Penny. It's because of them we look smart, smart enough to solve such questions. :P
2013-10-18 19:37:30 Martijn Muijsers
@Pranay should be (4,4), author made a mistake.
2013-07-26 03:11:04 Pranay
how is movement to (3,4) from (4,5) (point 3 in shown example) valid for the given 4 movements ?
2013-07-25 05:42:26 Hamim Raavi
simple and elegant :)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.