Yet Another Counting Problem

题意翻译

给予两个数$a,b$，进行$q$次询问。对于每次询问，你需要回答： - 在$[l,r]$中，满足以下条件的$x$的个数： $(x \bmod a) \bmod b \neq (x \bmod b) \bmod a$ **输入有多组数据**（$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}$

题目描述

You are given two integers $ a $ and $ b $ , and $ q $ queries. The $ i $ -th query consists of two numbers $ l_i $ and $ r_i $ , and the answer to it is the number of integers $ x $ such that $ l_i \le x \le r_i $ , and $ ((x \bmod a) \bmod b) \ne ((x \bmod b) \bmod a) $ . Calculate the answer for each query. Recall that $ y \bmod z $ is the remainder of the division of $ y $ by $ z $ . For example, $ 5 \bmod 3 = 2 $ , $ 7 \bmod 8 = 7 $ , $ 9 \bmod 4 = 1 $ , $ 9 \bmod 9 = 0 $ .

输入输出格式

输入格式

The first line contains one integer $ t $ ( $ 1 \le t \le 100 $ ) — the number of test cases. Then the test cases follow. The first line of each test case contains three integers $ a $ , $ b $ and $ q $ ( $ 1 \le a, b \le 200 $ ; $ 1 \le q \le 500 $ ). Then $ q $ lines follow, each containing two integers $ l_i $ and $ r_i $ ( $ 1 \le l_i \le r_i \le 10^{18} $ ) for the corresponding query.

输出格式

For each test case, print $ q $ integers — the answers to the queries of this test case in the order they appear.

输入输出样例

输入样例 #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