BALL1 - Ball

On the rectangular chessboard of n x m square fields we choose one field adjacent to the edge of the chessboard, called the starting field. Then we put a ball in the center of this field and push it to roll through the chessboard. The diameter of the ball equals the width (and height) of chessboard field. The angle between the direction of ball movement and the edge of the chessboard equals 45 degrees. The ball bounces off the edges of the chessboard: if the ball touches the edge of the chessboard then each composite of its velocity perpendicular to the edge touched is reversed. At the start the ball is pushed toward increasing coordinates (when the starting field is a field of the highest coordinate, the ball bounces momentarily).

We assign a point to a field of the chessboard each time the point of adjacency between the ball and the chessboard enters the interior of the field. The game is over when a point is assigned to the starting field. What is the number of fields to which an odd number of points is assigned? The following figures illustrate the problem. The route of the ball is marked with a dashed line. Fields with the odd number of points are shadowed.

Task

Write a program which for each data set from a sequence of several data sets:

  • reads the dimensions of the chessboard and the coordinates of starting field from input,
  • computes the number of fields with the odd number of points,
  • writes the result to output.

Input

The first line of the input file contains one integer d, 1 <= d <= 10, which is the number of data sets. The data sets follow. Each data set occupies one line of the input file. Such a line consists of four integers x, y, a, b separated with single spaces. These integers are the x- and y-dimensions of the chessboard and x- and y-coordinates of the starting field, respectively. Integers x and y are greater than two, the number of fields of the chessboard does not exceed 109,the starting field is adjacent to the edge of the chessboard.

Output

The i-th line of output should contain one integer which is equal to the number of fields of the chessboard with the odd number of points.

Example

Sample input:
2
13 6 1 5
10 7 1 5

Sample output:
2 
22

Added by:adrian
Date:2004-06-06
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:III Polish Collegiate Team Programming Contest (AMPPZ), 1998

hide comments
2012-06-09 07:55:15 Sky
@Adrian could you give some more test cases? i am getting correct answer for these test cases but when i submit, result is wrong answer...
2011-06-12 13:40:09 Vilhelm von Ehrenheim
alone: It means the square gets a point each time the ball enters it... So one point means the ball has only been on the square once, two points means two times etc.

Last edit: 2011-06-12 13:40:56
2011-05-03 23:01:13 Santiago Zubieta
My guess is that if at the end the ball has nowhere to go and the line wasn't closed its just 2 squares.

If the line is closed, then you select every square the line touched (in intersections you deselect)
2010-03-07 11:53:58 alone
"We assign a point to a field of the chessboard each time the point of adjacency between the ball and the chessboard enters the interior of the field."



wht is meaning of this line...
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.