题目描述

给定偶数 $n$ 和 $1 \le l_1 < r_1 < l_2 < r_2 < \cdots < l_k < r_k \le n$，求有多少个长度为 $n$ 的合法括号序列 $s$，满足对任意 $1 \le i \le k$，都有 $s_{l_i} \ne s_{r_i}$。

答案对 $998244353$ 取模。

输入格式

从文件 bracket.in 中读入数据。

第一行一个整数 $T$，表示测试组数。

接下来描述 $T$ 组测试数据。对每组数据：

1. 第一行两个整数 $n,k$。
2. 接下来 $k$ 行，每行两个整数 $l_i,r_i$。

输出格式

输出到文件 bracket.out 中。

对每组测试数据输出一行一个整数，表示满足条件的合法括号序列数量，答案对 $998244353$ 取模。

样例 1 输入

2
6 0
8 2
1 3
5 8

样例 1 输出

5
3

样例 1 说明

对于第一组数据，共有 ((()))，(()())，(())()，()(())，()()() 这 $5$ 个合法括号序列满足条件。

对于第二组数据，满足条件的合法括号序列是 (()(()))，(())(())，(())()()。

样例 2 输入

1
40 8
1 4
6 11
13 14
16 22
24 27
29 30
32 36
38 39

样例 2 输出

21517240

数据范围

性质 A：保证 $r_i=l_i+1$。
性质 B：保证 $k=0$。

对于所有测试点，保证 $n$ 是偶数，$2 \le n \le 2 \times 10^5$，$\sum n \le 2 \times 10^5$，$0 \le k \le \dfrac{n}{2}$，$1 \le l_1 < r_1 < l_2 < r_2 < \cdots < l_k < r_k \le n$。