Modular Equations#1562
Sign in

Modular Equations

1 second
128 megabytes
Very easy

The laws of modular arithmetic are among the best weapons we have in our arsenal. We, the wannabe computer scientists, frequently use those laws to keep things manageable. For example, if we are to compute the units digit of

2^{35^{137^{14}}} - 2^{45^{147^{32}}}

we would be able to do that in a flash. However, if it requires dealing with equations involving modular arithmetic, many of us may not feel just as comfortable. Fear not; we are not going to daunt you with a system of gruesome modular equations, we will keep it small and simple. Given the intervals for three integers (a_{\min} \leq a \leq a_{\max}), (b_{\min} \leq b \leq b_{\max}), and (m_{\min} \leq m \leq m_{\max}), you are to find the number of triples (a, b, m) that satisfy the equation:

(a + b) \bmod m = (a - b) \bmod m

Here is a sample.

1 \leq a \leq 2, 2 \leq b \leq 4, 3 \leq m \leq 5

(1 + 2) \bmod 4 = 3 = (1 - 2) \bmod 4
(1 + 3) \bmod 3 = 1 = (1 - 3) \bmod 3
(1 + 4) \bmod 4 = 1 = (1 - 4) \bmod 4
(2 + 2) \bmod 4 = 0 = (2 - 2) \bmod 4
(2 + 3) \bmod 3 = 2 = (2 - 3) \bmod 3
(2 + 4) \bmod 4 = 2 = (2 - 4) \bmod 4

Input

The first line contains the number of test cases (1 \leq t \leq 20). Each of the next lines corresponds to a separate test case and contains three pairs of integers: a_{\min}, a_{\max}, b_{\min}, b_{\max}, m_{\min}, m_{\max}. It is guaranteed that -1000 \leq a_{\min} \leq a_{\max} \leq 1000, -1000 \leq b_{\min} \leq b_{\max} \leq 1000, 1 \leq m_{\min} \leq m_{\max} \leq 1000.

Output

For each test case, print on a separate line its number and the number of triples (a, b, m) that satisfy the modular equation.

Examples

Example 1

Loading
Loading