A13417 | Yet Another Counting Problem

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.