朵拉在画班级壁画时把油漆弄翻了。朵拉将壁画视为一个大小为 $n \times n$ 的矩阵 $b$。初始时，对于所有 $1 \le i, j \le n$，有 $b_{i,j} = 0$。

朵拉只有两把颜色不同的刷子。在一次操作中，她可以使用其中一把刷子对矩阵进行染色：

• 第一把刷子上的颜色为 1，可以对矩阵的一列进行染色。即，朵拉选择 $1 \le j \le n$，并将所有 $1 \le i \le n$ 的 $b_{i,j}$ 设为 $1$；
• 第二把刷子上的颜色为 2，可以对矩阵的一行进行染色。即，朵拉选择 $1 \le i \le n$，并将所有 $1 \le j \le n$ 的 $b_{i,j}$ 设为 $2$。

朵拉对矩阵进行染色，使得最终的矩阵 $b$ 仅包含 1 和 2。

对于一个矩阵 $b$，令 $f(b)$ 表示将初始矩阵（仅包含 0）转化为 $b$ 所需的最少操作次数。矩阵 $b$ 的美观度定义为：恰好使用 $f(b)$ 次操作将初始矩阵转化为 $b$ 的不同染色方案数。如果无法将初始矩阵转化为 $b$，则 $b$ 的美观度为 0。

然而，朵拉犯了一个均匀随机的错误；给定的矩阵 $a$ 与真实的矩阵 $b$ 相比，恰好有一个元素不同。也就是说，恰好存在一个位置 $(i, j)$ 满足 $a_{i,j} = 3 - b_{i,j}$。

请帮助朵拉计算真实矩阵 $b$ 的期望美观度模 $998\,244\,353$ 的值（所有 $n^2$ 种可能的错误发生概率均等）。

由于矩阵的大小过大，朵拉只会告诉你矩阵 $a$ 中颜色为 1 的 $m$ 个元素的位置，其余 $n^2 - m$ 个元素颜色均为 2。

输入格式

每个测试点包含多个测试用例。第一行包含一个整数 $t$ ($1 \le t \le 10^4$) —— 测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 2 \cdot 10^5$, $0 \le m \le \min(10^6, n^2)$) —— 矩阵的大小和颜色为 1 的元素数量。

接下来 $m$ 行，每行包含两个正整数 $x_i$ 和 $y_i$ ($1 \le x_i, y_i \le n$) —— 表示 $a_{x_i,y_i} = 1$。

保证如果 $i \ne j$，则 $(x_i, y_i) \ne (x_j, y_j)$。

同时保证所有测试用例中 $n$ 的总和不超过 $4 \cdot 10^5$，所有测试用例中 $m$ 的总和不超过 $10^6$。

输出格式

对于每个测试用例，输出一个整数 —— 真实矩阵 $b$ 的期望美观度模 $998\,244\,353$ 的值。

样例

输入样例 1

7
2 2
1 1
1 2
2 1
1 1
3 2
1 1
3 3
6 0
5 10
1 1
1 2
1 3
2 1
2 3
5 1
5 2
5 3
5 4
5 5
3 5
1 1
1 3
2 2
3 1
3 3
4 3
1 1
2 3
2 4

输出样例 1

1
499122178
665496236
120
79859554
776412275
1

说明

在第一个测试用例中，矩阵 $a = \begin{bmatrix} 1 & 1 \\ 2 & 2 \end{bmatrix}$。为了计算答案，我们考虑改变元素 $(1, 1)$ 的情况。

可以证明，将初始矩阵染色为 $\begin{bmatrix} 2 & 1 \\ 2 & 2 \end{bmatrix}$ 的最少步数为 3。我们可以先将第一行染成颜色 2，然后将第二列染成颜色 1，最后将第二行染成颜色 2。过程如下：

$$\begin{bmatrix} 0 & 0 \\ 0 & 0 \end{bmatrix} \Rightarrow \begin{bmatrix} 2 & 2 \\ 0 & 0 \end{bmatrix} \Rightarrow \begin{bmatrix} 2 & 1 \\ 0 & 1 \end{bmatrix} \Rightarrow \begin{bmatrix} 2 & 1 \\ 2 & 2 \end{bmatrix}$$

可以证明，这是在 3 步内完成该矩阵染色的唯一方法。因此，矩阵 $\begin{bmatrix} 2 & 1 \\ 2 & 2 \end{bmatrix}$ 的美观度为 1。类似地，如果改变矩阵的任何其他元素，美观度也总是 1，因此真实矩阵 $b$ 的期望美观度为 1。

在第二个测试用例中，矩阵 $a = \begin{bmatrix} 1 & 2 \\ 2 & 2 \end{bmatrix}$。为了计算答案，我们考虑改变元素 $(2, 2)$ 的情况。

可以证明，无法将初始矩阵染色为 $\begin{bmatrix} 1 & 2 \\ 2 & 1 \end{bmatrix}$，因此其美观度为 0。

如果改变矩阵的任何其他元素，美观度总是 2，因此期望美观度为 $\frac{0+2+2+2}{4} = \frac{6}{4} \equiv 499\,122\,178 \pmod{998\,244\,353}$。