C. Очередная задача на подсчет
ограничение по времени на тест
3.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны два числа $$$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$$$.

Входные данные

В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Затем следуют сами наборы.

Первая строка каждого набора содержит три целых числа $$$a$$$, $$$b$$$ и $$$q$$$ ($$$1 \le a, b \le 200$$$; $$$1 \le q \le 500$$$).

Затем следуют $$$q$$$ строк, каждая из которых содержит два числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i \le r_i \le 10^{18}$$$) для очередного запроса.

Выходные данные

Для каждого набора тестовых данных выведите $$$q$$$ целых чисел — ответы на запросы в том порядке, в котором они задаются.

Пример
Входные данные
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