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

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

1 секунда

128 мегабайтів

Дуже легка

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

2^{3 5^{13 7^{14}}} - 2^{4 5^{14 7^{32}}}

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

ми можемо зробити це миттєво. Однак, працюючи з рівняннями на модуль, багато хто з нас може зазнати труднощів. Не хвилюйтеся; ми не будемо лякати вас складною системою модульних рівнянь — задача проста. Для трьох цілих чисел $a$ ( $a_{m i n} \leq a \leq a_{m a x}$ a_{\min} \leq a \leq a_{\max}), $b$ ( $b_{m i n} \leq b \leq b_{m a x}$ b_{\min} \leq b \leq b_{\max}) і $m$ ( $m_{m i n} \leq m \leq m_{m a x}$ m_{\min} \leq m \leq m_{\max}) задані інтервали значень. Визначте кількість трійок $(a, b, m)$ (a, b, m), що задовольняють рівняння:

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

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

Ось приклад:

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

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

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

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

(1 + 3) \bmod 3 = 1 = (1 - 3) \bmod 3

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

(1 + 4) \bmod 4 = 1 = (1 - 4) \bmod 4

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

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

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

(2 + 3) \bmod 3 = 2 = (2 - 3) \bmod 3

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

(2 + 4) \bmod 4 = 2 = (2 - 4) \bmod 4

Вхідні дані

Перший рядок містить кількість тестів $t$ ( $1 \leq t \leq 20$ 1 \leq t \leq 20). Кожен з наступних $t$ рядків містить три пари цілих чисел: $a_{m i n}$ a_{\min}, $a_{m a x}$ a_{\max}, $b_{m i n}$ b_{\min}, $b_{m a x}$ b_{\max}, $m_{m i n}$ m_{\min}, $m_{m a x}$ m_{\max}. Гарантується, що $- 1000 \leq a_{m i n} \leq a_{m a x} \leq 1000$ -1000 \leq a_{\min} \leq a_{\max} \leq 1000, $- 1000 \leq b_{m i n} \leq b_{m a x} \leq 1000$ -1000 \leq b_{\min} \leq b_{\max} \leq 1000, $1 \leq m_{m i n} \leq m_{m a x} \leq 1000$ 1 \leq m_{\min} \leq m_{\max} \leq 1000.

Вихідні дані

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

Приклади

Приклад 1

Loading

2^{3 5^{13 7^{14}}} - 2^{4 5^{14 7^{32}}}

a_{m i n} \leq a \leq a_{m a x}

b_{m i n} \leq b \leq b_{m a x}

m_{m i n} \leq m \leq m_{m a x}

(a, b, m)

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

1 \leq a \leq 2

2 \leq b \leq 4

3 \leq m \leq 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

1 \leq t \leq 20

a_{m i n}

a_{m a x}

b_{m i n}

b_{m a x}

m_{m i n}

m_{m a x}

- 1000 \leq a_{m i n} \leq a_{m a x} \leq 1000

- 1000 \leq b_{m i n} \leq b_{m a x} \leq 1000

1 \leq m_{m i n} \leq m_{m a x} \leq 1000

(a, b, m)