C. Assign or Multiply
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Zayin have a number $$$x$$$ which initially is equal to $$$1$$$, a prime number $$$p$$$, and $$$n$$$ operations, where the $$$i$$$-th operation must be one of the followings:

  • $$$x$$$:=$$$a_i$$$: assign the value $$$a_i$$$ to $$$x$$$
  • $$$x$$$*=$$$a_i$$$: assign the value $$$(x\times a_i)\ modulo\ p$$$ to $$$x$$$

Zayin will perform the $$$n$$$ from left to right, for example, if $$$p=7$$$ and there are $$$3$$$ operation - $$$x$$$:=$$$1$$$, $$$x$$$:=$$$2$$$, $$$x$$$*=$$$3$$$ respectly, the value of $$$x$$$ is $$$6$$$ eventually.

But Ziyin, as the naughty girlfriend of Zayin, may shuffle the operations randomly. In spite of that, Zayin found that some values would never be introduced no matter how the operations is shuffled, for example, the value $$$0,4,5$$$ can't be calculated no matter how $$$x$$$:=$$$1$$$, $$$x$$$:=$$$2$$$, $$$x$$$*=$$$3$$$ is shuffled.

Zayin is curious about how many values between $$$0$$$ and $$$p-1$$$ (both inclusively) can't be calaculated, can you help him?

Input

The first line of input contains two integers $$$p\ (2\le p\le 2\times 10^5)$$$, $$$n\ (1\le n\le 10^6)$$$.

The each line of the next $$$n$$$ lines contains two numbers $$$op_i$$$ and $$$a_i$$$ — if $$$op_i=0$$$, the $$$i$$$-th operation is $$$x$$$:=$$$a_i$$$, otherwise it's $$$x$$$*=$$$a_i$$$. ($$$0\le a_i \lt p$$$)

It's guranteed that $$$p$$$ is a prime number.

Output

print a integer, indicating how many values between $$$0$$$ and $$$p-1$$$ (both inclusively) can't be calaculated no matter how the operations is shuffled.

Example
Input
19 3
0 5
1 7
1 17
Output
15