Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3484
How Many Parallelograms on the Grids?

Time Limit: 3 Seconds      Memory Limit: 65536 KB

In geometry, a parallelogram is a quadrilateral with two pairs of parallel sides. Given n, you are asked to count the number of different parallelograms that sactisfy the following conditions:

  • All the vertices of the parallelogram are on the grid point, e.g., their coordinates are all integers.
  • The lengths pair of parallel sides are in the range of [a, b], while the lengths of the other pair atr in the rangeof [c, d].

Note that congruent parallelograms like the two in the figure below are counted as only one.


There are multiple test cases. The first line of input is an integer T indicating the number of test cases. (0 < T ≤ 100000)

Each test case consists of a line containing four possitive real number a, b, c and d(0 < ab ≤ 50, 0 < cd ≤ 50). There are at most 2 digits after the floating point for each real number.


For each test case, output the number of different paralleograms in one line.

Sample Input

1 1 1 1
1 1.5 1 1
1 2 1 2

Sample Output


Author: GUAN, Yao
Contest: The 11th Zhejiang University Programming Contest
Submit    Status