There are n stops on the sight seeing route of Syrjälä. The stops are numbered 1,2,\dots,n and are arranged in a cycle so associate n+1 = 1, n+2 = 2 and so on. There are also q buses numbered 1,2,\dots,q. The i-th bus begins it's tour at stop b_i and stops at every a_i-th stop until it returns to b_i. It can be proven that the bus will always return. For the i-th bus, print how many stops it visits on it's tour.

Input

The first line contains two integers n and q. The i-th line of following q lines, contains two integers a_i and b_i.

Output

Print the answer to the i-th bus on the i-th line.

Constraints

• 1 \leq n \leq 10^9
• 1 \leq q \leq 10^5
•  1 \leq a_i, b_i \leq n

Example

Input:

6 6
6 5
2 4
1 1
3 5
2 6
4 1

Output:

1
3
6
2
3
3

Explanation:

The paths for the queries are
5 -> 5
4 -> 6 -> 2 -> 4
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 1
5 -> 2 -> 5
6 -> 2 -> 4 -> 6
1 -> 5 -> 3 -> 1