题目描述

慧音老师一直很担心琪露诺的数学，教了⑨年依然没有半点长进。无奈之下她只好让琪露诺加训，还花大价钱请了城管博丽灵梦全程监督。
这次加训的内容是：给定一个长为$N$的整数序列$\{a_i\}, i = 0,1 \cdots N-1$，初始时所有值均为0。现要对该序列作$K$次修改。每次修改给定两个参数$c, r$，对于序列中每个数$a_i$，令$a_i \gets a_i + \max (0, r - \lvert i - c \rvert)$（其中箭头符号表示赋值）。
$K$次修改之后，琪露诺需要统计有多少个$a_i$满足$a_i > a_{i-1}$且$a_i > a_{i+1}, i = 1, 2 \cdots N-2$
之前提到琪露诺很喜欢炫富，而灵梦生性见钱眼开。所以趁慧音老师不在的时候，她拿⑨⑨⑨张百元大钞收买了灵梦，然后又一次把锅甩给了你。

输入格式

每个测试文件有多组数据。第一行为一个正整数$T$，表示测试数据的组数；
之后每组测试数据，第一行是两个正整数$N, K$；之后$K$行，每行两个非负整数$c, r$，表示该次修改的参数。输入保证$0 \le c<N, \quad 0<r \le N$

输出格式

每组测试数据输出一行，表示答案。

样例

输入

1
10 3
3 2
7 4
5 1

输出

1

样例说明

第一次修改后的序列为：$0, 0, 1, 2, 1, 0, 0, 0, 0, 0$
第二次修改后：$0, 0, 1, 2, 2, 2, 3, 4, 3, 2$
第三次修改后：$0, 0, 1, 2, 2, 3, 3, 4, 3, 2$

数据规模及约定

$T \le 5, \quad N, K \le 10^5$
本题共10个测试文件，部分测试点满足如下限制：
测试点#1~2：$N, K \le 1000$
测试点#3：$r \le 100, \quad 0 \le c - r < c + r < N$
测试点#4~5：$r \le 100$
测试点#6：$0 \le c - r < c + r < N$

时空限制

时间限制1s，空间限制64MB。