Description

You have two positive integers $a,b$.

You also have a positive integer $q$, and you need to process $q$ queries.

For each query, you are given two positive integers $l,r$.

You need to find $\max\{(i \bmod a)+(i \bmod b)\}$, where $i$ is a positive integer and $i \in [l,r]$.

Input Format

The first line contains two positive integers $a,b$.

The second line contains one positive integer $q$.

The next $q$ lines each contain two positive integers $l,r$.

Output Format

For each query, output one line containing one integer, which is the answer.

5 7
4
1 5
5 7
33 34
34 35

8
7
10
10

Hint

For $30\%$ of the testdata, $1 \le q \le 10^3$ and $1 \le l \le r \le 10^3$.

For $70\%$ of the testdata, $1 \le q \le 10^3$ and $1 \le l \le r \le 10^9$.

For $100\%$ of the testdata, $1 \le a,b \le 10^3$, $1 \le q \le 10^5$, and $1 \le l \le r \le 10^9$.

Translated by ChatGPT 5