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 type-

• 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^8
1<=k<=20
0<=p<=1
0<=x<=10^8

Example

Input:
30
3
1 8
0 3
1 12

Output:
15
15
5