题目描述

慧音老师一直很担心琪露诺的数学，教了⑨年依然没有半点长进。无奈之下她只好让琪露诺加训，还花大价钱请了城管博丽灵梦全程监督。
这次加训的内容是：给定一个长为\(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。