# DSLCS 2011 Number Theory. Favorites

# Modular Equations

The laws of modular arithmetic are among the best weapons that 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 ^{3}5^{13}7^{14}** -

**2**

^{4}5^{14}7^{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; were not going to daunt you with a system of gruesome modular equations we would keep it small and simple. Given the range of three integers **a **(**amin** ≤ **a** ≤ **amax**), **b** (**bmin** ≤ **b** ≤ **bmax**) and **m** (**mmin** ≤ **m** ≤ **mmax**) you are to find the number of triples (**a**, **b**, **m**) that satisfy the equation:

(**a** + **b**) mod **m** = (**a** - **b**) mod **m**

Here is a sample.

**1** ≤ **a** ≤ **2**, **2** ≤ **b** ≤ **4**, **3 **≤ **m** ≤ **5**

**(1 + 2) mod 4 = 3 = (1 - 2) mod 4**

**( 1 + 3) mod 3 = 1 = (1 - 3) mod 3 **

**( 1 + 4) mod 4 = 1 = (1 - 4) mod 4 **

**( 2 + 2) mod 4 = 0 = (2 - 2) mod 4**

**(2 + 3) mod 3 = 2 = (2 - 3) mod 3 **

**(2 + 4) mod 4 = 2 = ( 2 - 4) mod 4 **

** Input**

The first line of the input gives you the number of test cases **t** (**1** ≤ **t** ≤ **20**). Each of the next **t** lines contains the input for each test case which is given by **3** pairs of integer **amin**, **amax**, **bmin**, **bmax** and **mmin**, **mmax**. You can assume that **-1000** ≤ **amin** ≤ **amax** ≤ **1000**, **-1000** ≤ **bmin** ≤ **bmax** ≤ **1000**, **1** ≤ **mmin** ≤ **mmax** ≤ **1000**.

** Output**

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

3 1 2 2 4 3 5 -100 100 200 350 1 1000 5 9 10 12 2 9

Case 1: 6 Case 2: 318384 Case 3: 45