You have just learned the algorithm bubble sort, which is able to sort an array in non-descending order. Let's define the function $\text{sort}(a)$ as in the following pseudocode:

function sort(array a):
    rounds := 0
    n := length of a
    while a is not non-decreasing:
        rounds := rounds + 1
        for i from 1 to n - 1:
            if a[i] > a[i + 1]:
                swap(a[i], a[i + 1])
    return rounds

As it is shown, the return value of $\text{sort}(a)$ represents the number of rounds needed to make array $a$ sorted in non-descending order by using bubble sort.

You are given an integer $n$, as well as $m$ integer tuples $(k_i,l_i,r_i)$ ($1\le i\le m$). Count the number of permutations$^{\text{∗}}$ $p$ of length $n$, modulo $998\,244\,353$, so that the following restrictions are satisfied:

• For each $1\le i\le n$, let $b_i=\text{sort}([p_1,p_2,\ldots,p_{i}])$, then
• For each $1\le j\le m$, let $x$ be the number of indices $y$ ($1\le y\le n$) such that $b_y\le k_j$, then $l_j\le x\le r_j$ holds.

$^{\text{∗}}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($2\leq n\leq 10^6$, $0\leq m\leq 1000$).

Then $m$ lines follow, the $i$-th line containing three integers $k_i$, $l_i$, and $r_i$ ($0\le k_i\le n - 1$, $1\le l_i\le r_i\le n$) — the restrictions.

It is guaranteed that the sum of $m^2$ over all test cases does not exceed $10^6$.

Output

For each test case, output a single integer — the number of possible permutations, modulo $998\,244\,353$.

Note

In the first test case, only permutations $[3,1,4,2]$ and $[4,1,3,2]$ satisfy the restrictions. Take $[3,1,4,2]$ as an example. Let's calculate the array $b$:

• $\text{sort}([3])=0$;
• $\text{sort}([3,1])=1$;
• $\text{sort}([3,1,4])=1$;
• $\text{sort}([3,1,4,2])=2$.

Thus, $b=[0,1,1,2]$. It is easy to show that it satisfies all the restrictions.

In the second test case, only permutation $[1,2,3]$ satisfies the restrictions.

In the third test case, the following $8$ permutations satisfy the restrictions:

• $[2,3,1,4]$;
• $[2,4,1,3]$;
• $[3,2,1,4]$;
• $[3,4,1,2]$;
• $[3,4,2,1]$;
• $[4,2,1,3]$;
• $[4,3,1,2]$;
• $[4,3,2,1]$.