Модулярні рівняння
Закони модулярної арифметики є кращою зброєю у нашому арсеналі. Ми, наслідувачі вчених, часто використовуємо ці закони для керування світом. Наприклад, якщо ми хочемо обчислити
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), які задовольняють модулярному рівнянню.