Ankur Sir, getting bored in class thinks of something to pass his time. He writes all the numbers from 0 to n-1 and then does k operations on these numbers. The operations are of two types:

• 0 x - Replace each number i by (i + x) mod n
• 1 x - Replace each number i by (i × x) mod n

Now he wants to know how many unique numbers are there after each such operation and has asked for your help.

Note- Each operation is done on the numbers that we get after the previous operation and not on the original.

Input

First line contains n
Second line contains k, the number of operations
Each of the next k lines contain 2 integer p and x

Output

Output k lines, each containing how many unique numbers are left.

Constraints

1 ≤ n ≤ 10⁸
1 ≤ k ≤ 20
0 ≤ p ≤ 1
0 ≤ x ≤ 10⁸

Example

Input:
30
3
1 8
0 3
1 12

Output:
15
15
5