Модулярные уравнения
Законы модулярной арифметики являются лучшим оружием в нашем арсенале. Мы, подражатели ученых, часто используем эти законы для управления миром. Например, если мы хотим вычислить
2^35^137^14 - 2^45^147^32
то это можно сделать в один миг. Однако для этого следует решить уравнения в модулярной арифметике, и многие из нас могут прийти в замешательство. Но не бойтесь; мы не будем устрашать Вас ужасной системой модулярных уравнений, мы дадим Вам простую задачку. По заданным интервалам трех целых чисел a (amin ≤ a ≤ amax), b (bmin ≤ b ≤ bmax) и m (mmin ≤ m ≤ mmax) Вам следует найти количество таких троек (a, b, m), которые удовлетворяют уравнению:
(a + b) mod m = (a - b) mod m
Рассмотрим пример.
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
Входные данные
Первая строка содержит количество тестов t (1 ≤ t ≤ 20). Каждая из следующих t строк является отдельным тестом и содержит три пары целых чисел amin, amax, bmin, bmax и mmin, mmax. Известно, что -1000 ≤ amin ≤ amax ≤ 1000, -1000 ≤ bmin ≤ bmax ≤ 1000, 1 ≤ mmin ≤ mmax ≤ 1000.
Выходные данные
Для каждого теста вывести в отдельной строке его номер и количество троек (a, b, m), удовлетворяющих модулярному уравнению.