Triangles in the Grid

There is a grid of n*m unit squares, which has n + 1 horizontal lines, m + 1 vertical lines and (n + 1)(m + 1) intersection vertices. You can choose three distinct non-collinear vertices to form a triangle. For example, if n = m = 1, there are 4 vertices, which can form 4 triangles.

How many of these triangles have area between A and B (inclusive)?

Input

The first line contains the number of test cases T (T $\le$ 25). Each test case contains four integer n, m, A, B (1 $\le$ n, m $\le$ 200, 0 $\le$ A < B $\le$ nm).

Output

For each test case, print the number of triangles whose area is between A and B, inclusive.

Sample Input

4
1 1 0 1
1 2 1 2
10 10 20 30
12 34 56 78

Sample Output

Problemsetter: Rujia Liu, Special Thanks: Feng Chen