DCEPC901 - Unique Numbers

no tags 

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

hide comments

Added by:dce coders
Date:2012-08-25
Time limit:0.204s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C C++ 4.3.2 CPP JAVA
Resource:Own Problem