C. 又一个计数问题
时间限制：3.5 秒
内存限制：256 兆字节

给定两个整数 $a$ 和 $b$，以及 $q$ 个查询。第 $i$ 个查询包含两个数字 $l_i$ 和 $r_i$，其答案是满足以下条件的整数 $x$ 的个数：

且

请计算每个查询的答案。

回忆：$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