1342C. C. Yet Another Counting Problem

CF1342C. Yet Another Counting Problem

时限: 3.5 秒 | 内存: 256 MB | 输入: 标准输入 | 输出: 标准输出

给定两个整数 $a$ 和 $b$，以及 $q$ 个询问。第 $i$ 个询问包含两个数 $l_i$ 和 $r_i$，你需要回答在区间 $l_i \le x \le r_i$ 内，有多少个整数 $x$ 满足 $((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$），表示测试用例的数量。接下来是 $t$ 组测试用例。

每组测试用例的第一行包含三个整数 $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$ 个整数，分别表示每个询问的答案。

样例输入 1

2
4 6 5
1 1
1 3
1 5
1 7
1 9
7 10 2
7 8
100 200

样例输出 1

0 0 0 2 4 
0 91