题目描述
给定两个正整数 $a$ 和 $b$，以及 $q$ 次询问。
对于每次询问，给定两个整数 $l_i, r_i$，你需要求出在区间 $[l_i, 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$，表示测试用例的数量。
接下来 $t$ 组测试用例，每组格式如下：
第一行三个正整数 $a, b, q$。
接下来 $q$ 行，每行两个正整数 $l_i, r_i$，表示一次询问。
输出格式
对于每组测试用例，输出一行 $q$ 个整数，第 $j$ 个整数表示第 $j$ 次询问的答案。相邻两个整数之间用一个空格隔开。
输入输出样例
输入 #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样例解释
第一组测试用例 $a = 4, b = 6$：
- 区间 $[1, 1]$、$[1, 3]$、$[1, 5]$ 内没有满足条件的整数；
- 区间 $[1, 7]$ 内满足条件的是 $x = 6, 7$，共 $2$ 个；
- 区间 $[1, 9]$ 内满足条件的是 $x = 6, 7, 8, 9$，共 $4$ 个。
第二组测试用例 $a = 7, b = 10$：
- 区间 $[7, 8]$ 内的 $x = 7, 8$ 均不满足条件；
- 区间 $[100, 200]$ 内有 $91$ 个满足条件的整数。
数据范围与提示
本题采用子任务制评分。
| 子任务 | 分值 | $t$ | $a, b$ | $q$ | $l_i, r_i$ |
|---|---|---|---|---|---|
| Subtask 1 | $30$ | $\le 10$ | $\le 30$ | $\le 10$ | $\le 10^6$ |
| Subtask 2 | $70$ | $\le 100$ | $\le 200$ | $\le 500$ | $\le 10^{18}$ |
对于 $100\%$ 的数据，$1 \le t \le 100$，$1 \le a, b \le 200$，$1 \le q \le 500$，$1 \le l_i \le r_i \le 10^{18}$。