Вам даны два числа \(a\) и \(b\), а также \(q\) запросов. \(i\)-й запрос состоит из двух чисел \(l_i\) и \(r_i\), и ответ на него — количество таких целых чисел \(x\), что \(l_i \le x \le r_i\) и \(((x \bmod a) \bmod b) \ne ((x \bmod b) \bmod a)\). Вычислите ответ на каждый запрос.
Напоминаем, что \(y \bmod z\) — остаток от деления \(y\) на \(z\). Например, \(5 \bmod 3 = 2\), \(7 \bmod 8 = 7\), \(9 \bmod 4 = 1\), \(9 \bmod 9 = 0\).
Выходные данные
Для каждого набора тестовых данных выведите \(q\) целых чисел — ответы на запросы в том порядке, в котором они задаются.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
4 6 5
1 1
1 3
1 5
1 7
1 9
7 10 2
7 8
100 200
|
0 0 0 2 4
0 91
|