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.
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:
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.
3 3 2 7 8 5 1 10 8 2 1 50 50
17 30 50
* First data set is the example in the diagram above.