题目背景

MX 在研究排列所具有的性质。这一天，她拿出了 $n$ 张卡片排成一排，想要在上面填数以写成一个 $1\sim n$ 的排列。

Piggy 趁 MX 不注意，偷偷在一些卡片上写了数。

题目描述

MX 很快发现了这一切。不过她并不生气，而是考虑一个有趣的问题：如果我在上面填一些数，让它依然构成一个排列，且它的最长上升子序列长度为 $n-1$，MX 有多少种填数方法呢？

Piggy 比较良心。他没有在不同的位置上填相同的数。

输入格式

本题有多组测试数据。

第一行一个整数 $T$ 代表数据组数。
对于每组数据：

• 第一行两个整数 $n,q$ 代表卡牌个数和 Piggy 已经填上了多少个数。
• 第二行 $2q$ 个整数，第 $2i-1,2i$ 个整数 $(x,y)$ 代表第 $x$ 个数被 Piggy 填成了 $y$。

输出格式

输出 $T$ 行，每行一个整数代表答案。

2
10 4
2 2 4 8 6 5 7 6
2 0

1
1

2
40 21
1 1 2 2 6 6 7 7 8 8 9 9 10 10 11 11 15 15 16 16 23 23 24 24 25 25 26 26 30 30 34 35 35 36 36 37 37 38 38 39 40 40
40 15
3 3 4 4 14 14 15 15 17 17 19 19 24 23 25 24 27 26 30 29 31 30 33 32 35 34 39 38 40 39

4
4

提示

样例解释

用 $-1$ 代表此位置数字还未确定。
样例 $1$：第一组给定的排列为 $-1,2,-1,8,-1,5,6,-1,-1,-1$。容易发现，只有 $1,2,3,8,4,5,6,7,9,10$ 的最长上升子序列长度为 $10-1=9$。第二组给定的排列为 $-1,-1$，$2,1$ 为唯一满足要求的序列。

本题采用捆绑测试。

保证 $0\le q\le n$，$1\le n\le 5\times 10^5$，$1\le T\le 10^5$，$1 \le x,y \le n$。