#1545 FloorTiling

57  1 s   128 MB  

Description

 

You are tiling a floor that is width by height units. You are using strips of tile that are size by 1 units. The long side of the tiles should run along the side of the floor that is width units long. See the diagram for more details on exactly how the tiles should be placed.

 

 

 

 

Note how each row is offset by offset units from the one below it. (When thinking of how to offset the rows, imagine infinite horizontal strips of tiles.) Also, notice that the bottom row is touching the side. As the diagram illustrates, you will not be able to tile the whole floor with pieces that are size by 1.

 

 

 

Input

The input consists of several data sets. The first line of the input file contains the number of data sets which is a positive integer.

 

Each data set consists of 4 integers. <size> <offset> <width> <height>

 

You can assume the following:

  1. offset will be between 0 and size-1, inclusive.
  2. size will be between 2 and floor(width/2), inclusive.
  3. width and height will each be between 4 and 50, inclusive.

 

 

 

Output

 

For each data set, print the area of the region that will not be covered when tiling according to the strategy shown in the image.

 

 

 

Sample Input

Sample Output

3
3 2 7 8
5 1 10 8
2 1 50 50
17
30
50

HINT

* First data set is the example in the diagram above.

 

Source

TCO 2005, Round 2, Easy