问题描述

给定一个 质数 $p$ 和 $n$ 个操作，操作有如下两种：

• 给定 $x$，将 $w$ 修改为 $x$。

• 给定 $x$，将 $w$ 修改为 $(w\times x)\bmod p$。

其中 $w$ 是一个初始为 $1$ 的变量。

你可以以任意顺序执行上面的 $n$ 个操作，得到最终的 $w$。你需要求出在 $0\sim p-1$ 中，有多少个数是 无论以什么顺序执行操作 都无法得到的。

输入格式

本题为多组数据，输入数据第一行包含一个整数 $T$，表示数据组数。

对于每组数据：

第一行包含两个整数 $p,n$。

接下来 $n$ 行，每行包含两个整数 $op_i,x_i$。其中 $op_i=0$ 表示第一种操作，$op_i=1$ 表示第二种操作，$x_i$ 表示操作中给定的数。

输出格式

对于每组数据，输出一行一个整数表示答案。

输入样例1

1
7 3
1 2
0 6
1 3

输出样例1

3

样例1解释

$0, 2, 3$ 无法被生成。

数据范围

对于所有数据，保证 $1\le T\le 2$，$1\le n\le 10^6$，$2\le p\le 10^6$，$op_i\in \{0,1\}$，$0\le x_i < p$。保证 $p$ 为质数。

特殊性质 A：保证最多存在 $12$ 个第二种操作。