You are given a grid of size N∗M. The rows are numbered from 0 to N−1, and the columns are numbered from 0 to M−1.
In a single move, you can go from (x,y) to ((x+A)modN,y) or (x,(y+B)modM) where A and B are positive integers satisfying 1≤A≤N−1 and 1≤B≤M−1.
You are also given Q queries. You have to solve each query independently.
In each query, you will be given two positions (x1, y1) and (x2, y2). You have to find the number of possible pairs of (A, B) so that (x2, y2) is reachable from (x1, y1) using any number of moves (possibly zero).
Input Format:
The first line of the input contains two space-separated integers N and M representing the size of the grid.
The next line contains a single integer Q representing the number of queries.
The next Q lines contain 4 space-separated integers x1, y1, x2, y2.
Output Format:
Output Q lines, where the ith line represents the answer to the ith query.
Constraints:
2≤N,M≤105
1≤Q≤105
0≤x1,x2≤N−1
0≤y1,y2≤M−1
In the first query, possible pairs of (A, B) are {(1, 1), (1, 3)}.
In the second query, possible pairs of (A, B) are {(1, 1), (1, 2), (1, 3)}.
