Вам даны два числа \(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
3500 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач