e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Змагання

ДЛКШ-2011 Теорія чисел. Вибране

Модулярні рівняння

Закони модулярної арифметики є кращою зброєю у нашому арсеналі. Ми, наслідувачі вчених, часто використовуємо ці закони для керування світом. Наприклад, якщо ми хочемо обчислити

23513714 - 24514732

то це можна зробити миттєво. Проте для цього потрібно розв'язати рівняння у модулярній арифметиці, і багато з нас можуть прийти у недоуміння. Але не бійтесь; ми не будемо лякати Вас жахливою системою модулярних рівнянь, ми дамо Вам просту задачку. За заданими інтервалами трьох цілих чисел a (aminaamax), b (bminbbmax) та m (mminmmmax) Вам потрібно знайти кількість таких трійок (a, b, m), які задовольняють рівнянню:

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

Розглянемо приклад.

1a2, 2b4, 3 m5

(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 (1t20). Кожний з наступних t рядків є окремим тестом і містить три пари цілих чисел amin, amax, bmin, bmax та mmin, mmax. Відомо, що -1000aminamax1000, -1000bminbmax1000, 1mminmmax1000.

Вихідні дані

Для кожного тесту вивести в окремому рядку його номер та кількість трійок (a, b, m), які задовольняють модулярному рівнянню.

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #1
3
1 2 2 4 3 5
-100 100 200 350 1 1000
5 9 10 12 2 9
Вихідні дані #1
Case 1: 6
Case 2: 318384
Case 3: 45