After having a romantic night at the boat, Jon Snow and our Khaleesi Dany decided to "jump" to a conclusion. They intend to implement this by literally jumping on a series of rocks in a line along the seashore. Since they're too deep in love, they'll only consider those points where they both will meet.

You are given 2 numbers A and B one for Jon and the other for Dany. Jon jumps by A steps and Dany jumps by B steps. You are also given Q queries, each containing a range [L, R]. It may be possible that L > R, in which you'll have to swap the numbers to get desired range. Find the numbers of points for each range where both Jon and Dany will meet. Both start at 0.

Input Format

First line contains 3 integers - A, B and Q. Each of the next Q lines contains 2 integers L and R.

Constraints

1 <= A,B <= 10^9

1 <= Q <= 10^5

1 <= L,R <= 10^9

Output Format

Print a number for each query denoting the number of meeting points of Jon and Dany i.e. number of common points of Jon and Dany.