Silver187 喜欢排列。对于一个长度为 $n$ 的排列 $P$，位置 $x(2 \le x \le n - 1)$ 是一个“好位置”，当且仅当 $\forall 1 \le i \le x - 1, P_i < P_x$ 且 $P_x > P_{x+1}$。特别地： 1. 位置 $1$ 是一个好位置，当且仅当 $P_1 > P_2$ 且 $n \ge 2$。 2. 位置 $n$ 永远不可能是好位置。

Silver187 想要计算排列 $P$ 的“优美值”。他定义了一个数 $S$，初始时 $S = 0$。Silver187 会对排列 $P$ 重复执行以下操作，直到排列 $P$ 变为升序： 1. 将当前排列 $P$ 中好位置的数量累加到 $S$ 中。 2. 对排列 $P$ 进行一次冒泡排序（对于每个 $i$ 从 $1$ 到 $n - 1$ 按顺序执行，如果 $P_i > P_{i+1}$，则交换 $P_i, P_{i+1}$）。

$S$ 即为排列 $P$ 的优美值。

Silver187 给你两个数 $n$ 和 $m$。共有 $m$ 个约束条件。每个约束条件给出 $x$ 和 $y$，表示位置 $x$ 上的初始数值为 $y$。求所有满足所有约束条件的排列的优美值之和，结果对 $998244353$ 取模。

输入格式

第一行包含一个整数 $T(1 \le T \le 100)$，表示测试用例的数量。 每个测试用例中： 第一行包含两个整数 $n(1 \le n \le 10^6)$ 和 $m(0 \le m \le n)$，分别表示排列的长度和约束条件的数量。 接下来的 $m$ 行，每行包含两个整数，表示第 $i$ 个约束条件。 保证至少存在一个满足所有约束条件的排列。 输入保证 $1 \le \sum m \le \sum n \le 10^7$。

输出格式

对于每个测试用例，输出一个整数，表示所有满足约束条件的排列的优美值之和，结果对 $998244353$ 取模。

样例

样例输入 1

2
3 1
1 2
7 5
4 5
2 2
6 7
3 3
1 4

样例输出 1

3
13