该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

双重取模警报

题目背景

在 模运算实验室 中，研究员会对同一个整数 $x$ 进行两种不同顺序的 双重取模 运算，用来检测系统是否出现异常。由于设备结构不同，两种顺序可能产生不同结果，从而触发报警。

题目描述

给定两个正整数 $a,b$。对任意非负整数 $x$，定义两种运算结果：

• 方案 A：$$F(x)=((x\bmod a)\bmod b)$$
• 方案 B：$$G(x)=((x\bmod b)\bmod a)$$

如果某个整数 $x$ 满足 $F(x)\ne G(x)$，则称 $x$ 为一个 异常数 （会触发警报）。

你将收到 $q$ 次查询，每次给出一个区间 $[l_i,r_i]$，请你计算：在该区间内一共有多少个整数 $x$ 是异常数。

说明：$u\bmod v$ 表示 $u$ 除以 $v$ 的余数。

输入格式

第一行一个整数 $t$，表示测试用例数量。

接下来对于每个测试用例：

• 第一行三个整数 $a,b,q$；
• 接下来 $q$ 行，每行两个整数 $l_i,r_i$，表示一次查询区间。

输出格式

对每个测试用例，输出一行，包含 $q$ 个整数（用空格分隔），依次表示每个查询 $[l_i,r_i]$ 内异常数的个数。

样例输入输出

样例输入

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

样例解释

以第一组测试用例 $a=4,b=6$ 为例：

• 在区间 $[1,5]$ 内没有异常数，所以输出为 $0$；
• 在区间 $[1,7]$ 内有 $2$ 个整数会触发 $F(x)\ne G(x)$，因此该次输出为 $2$。 （其余查询同理。）

数据范围与约定

• $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}$

子任务划分