Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Wireless Signal

By curly_braces · Limits 1s, 256 MB

The city of Byteland is rectangular in shape and can be represented as a 2D coordinate system with nn columns and mm rows. At each of the intersections, there is a house. The top left house of the city is situated at coordinate (0,m1)(0, m-1) and the bottom right house is situated at (n1,0)(n-1, 0). The town hall is situated at the coordinate (x,y)(x, y) which contains a cell tower providing wireless network signal to all the houses in Byteland. Judges will be moving to Byteland soon. Wireless signal travels in a straight line and it gets weakened only if the signal has to travel straight through another house, judges want to choose a house in such a way that their devices receive maximum possible signal strength.

Can you tell me how many different houses meet judges’ requirements?

Note: Judges can not move to the town hall as the mayor lives there. The width and length of the houses are so small that you can ignore them.

Input

The first line of the input will contain a single integer T(1T106)T(1 \leq T \leq 10^6), denoting the number of test cases.

The next TT lines will contain four integers n,m,x,y(1n,m106;0x<n;0y<m)n, m, x, y(1 \leq n,m \leq 10^6; 0 \leq x < n; 0 \leq y < m) each.

It is guaranteed that sum of max(n,m)max(n,m) in all the test cases doesn’t exceed 107.10^7.

Output

For each test case, print an integer containing the answer.

Sample

InputOutput
3
1 1 0 0
2 3 1 1
4 4 1 1
0
5
12

In the first case, there are no houses available.

In the second case, all houses but the town hall meets the requirements. In the third case, 12 houses meet the requirements


Discussion

Statistics


46% Solution Ratio

aritra741Earliest, 2M ago

fextivityFastest, 0.1s

tanvirtareqLightest, 5.5 MB

tanvirtareqShortest, 927B

Submit

Login to submit

Editorial

A house will have maximum signal strength if the signal doesn’t have to travel through another house...

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.