Maximum Modular Sum Query

You are given two positive integers a and b. You are also given a positive integer q representing the number of queries. For each query, you will be given two positive integers l and r. Your task is to find the maximum value of

for all positive integers i such that l \le i \le r. Note that the mod operation yields the remainder upon division.

Hint: Since the function f(i) is periodic with period \(\text{lcm}(a,b)\), you can precompute the function over one period and use it to answer queries efficiently, especially when the query range is large.

inputFormat

The first line contains two space-separated positive integers a and b.

The second line contains one positive integer q, the number of queries.

Each of the next q lines contains two space-separated integers l and r representing one query.

It is guaranteed that all input values are valid positive integers.

outputFormat

For each query, output one line containing the maximum value of (i mod a) + (i mod b) for all integers i within the range [l, r].

sample

5 7
3
1 10
2 20
10 100

8
9
10