Problem Description

Silver187 likes Permutation. For a permutation $P$ of length $n$, a position $x(2\le x\le n-1)$ is a good position if and only if $\forall 1\le i\le x-1$,$P_i\lt P_x$, and $P_x \gt P_{x+1}$. In particular:
1. position $1$ is a good position if and only if $P_1>P_2$ and $n\geq 2$.
2. position $n$ can never be a good position.

Silver187 wants to calculate the beauty value of a permutation $P$ of length $n$. He defines a number $S$, initially $S=0$. Silver187 will repeat the following operations for the permutation $P$ until the permutation $P$ is in ascending order.

1. Add to $S$ the number of good positions in the current permutaion $P$.

2. Do a bubble sort on the permutation $P$(For each $i$ from $1$ to $n - 1$ in order, if $P_i$ > $P_{i+1}$, swap $P_i$, $P_{i+1}$).

$S$ is the beautiful value of the permutation $P$.

Silver187 gives you two numbers $n$ and $m$. There are $m$ constraints. Every constraint will give $x$ and $y$, which means the inital number of position $x$ is $y$. Find the sum of the beauty values of all permutations that satisfy all constraints modulo $998244353$.

Input

The first line has one integer $T(1≤T≤100)$, indicating there are $T$ test cases.

In each case:

The first line contains two integers $n(1\le n\le 10^6)$, $m(0\le m\le n)$---the length of the permutation and the number of constraints.

The $i$-th line of the next $m$ line contains two integers---the $i$-th constraint.

It is guaranteed that there is at least one permutation that satisfies all constraints.

Input guarantee $1\le \sum m\le \sum n\le 10^7$.

Output

In each case, output a single integer---the sum of the beautiful values of all permutations that satisfy the constraints modulo $998244353$.

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

3
13