给你两个整数 $$$a$$$ 和 $$$b$$$,以及 $$$q$$$ 查询。第 $$$i$$$ 查询由两个数字 $$$l_i$$$ 和 $$$r_i$$$ 组成,其答案是满足 $$$l_i \le x \le r_i$$$ 和 $$$((x \bmod a) \bmod b) \ne ((x \bmod b) \bmod a)$$$ 的整数 $$$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$$$ 整数 - 该测试用例的查询的答案按照出现的顺序排列。
示例
输入 #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