题目描述

给定一个整数 $p$ 和 $n$ 个操作，操作有如下两种： 1. 给定 $x$，将 $w$ 修改为 $x$。 2. 给定 $x$，将 $w$ 修改为 $(w+x)\bmod p$。 其中 $w$ 是一个初始为 $0$ 的变量。 你可以以任意顺序执行上面的 $n$ 个操作，得到最终的 $w$。你需要求出在 $0\sim p-1$ 中，有多少个数是无法得到的。

输入格式

本题为多组数据，输入数据第一行包含一个整数 $T$，表示数据组数。 对于每组数据： 第一行包含两个整数 $p,n$。 接下来 $n$ 行，每行包含两个整数 $op,x$。其中 $op=0$ 表示第一种操作，$op=1$ 表示第二种操作，$x$ 表示操作中给定的数。

输出格式

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

样例

样例 #1 输入

1
6 3
1 2
0 3
1 1

样例 #1 输出

2

样例 #1 解释

$1,2$ 无法被生成。

其余样例见下发文件

数据范围与约定

对于所有数据，$1\le T\le 2,1\le n\le 10^6,2\le p\le 10^6,\sum n\le 1.1\times 10^6,op\in {0,1},0\le x\le p$。