Welcome to ZOJ
Information
Problems
Runs
Statistics
Ranklist
Clarification
104 - The 11th Zhejiang University Programming Contest - H
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.

Input

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.

Output

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

Sample Input

3
1 1 1 1
1 1.5 1 1
1 2 1 2

Sample Output

1
2
6


Author: Local Contests 2011 Committee
Contest: The 11th Zhejiang University Programming Contest
Submit    Status