妹滋滋是一个善于编程的女孩子。

但是某一天，她一不小心把 UOJ 后台的票数统计程序写错了。

本来嘛在这种根本没有什么用的功能上出了 bug 也没有什么大关系，但是又有某一天，UOJ 突然就开始搞全民公投了。

这可怎么办呢？如果这个消息让别人知道的话自己肯定会被查表，更不要说让所有用户重新来投一次票了。

作为一个要强的女孩子，妹滋滋决定自力更生。

通过一些奥妙重重的方式，妹滋滋知道了一些关于这次全民公投的信息。

1. 这次全民公投一共有 $n$ 位用户排队参加，编号为 $1$ 到 $n$。每一位用户要么投了通过，要么投了不通过。
2. 有 $m$ 个二元组 $(x_i,y_i)$，每个二元组给出这样一个信息： “前 $x_i$ 位用户中，恰好 $y_i$ 位投了通过” 和 “后 $y_i$ 位用户中，恰好有 $x_i$ 位投了通过” 这两句话中，至少有一句是成立的。

作为分析的第一步，她想要知道有多少种投票情况是满足她所得到的信息的。当然，可能所有投票情况都不满足条件。

输入格式

输入第一行一个正整数 $T$ 表示数据组数。

对于每组数据，第一行有两个空格隔开的正整数 $n,m$。

接下来 $m$ 行每行两个空格隔开的正整数 $x_i,y_i$，保证 $0\le x_i,y_i\le n$ 且 $x_i,y_i$ 不全为 $0$。

输出格式

对于每组数据输出一行表示答案，答案可能很大，只需要输出对 $998244353$（$7\times 17\times 2^{23}+1$，一个质数） 取模后的值。

样例一

input

2
3 1
2 1
5 3
1 3
4 2
3 1

output

4
2

explanation

用 $0$ 表示不通过，$1$ 表示通过。

满足第一组数据的情况有：$(100),(101),(010),(011)$。

满足第二组数据的情况有：$(10010),(01010)$。

样例二

见样例数据下载。

限制与约定

对于所有数据，$T\le 5$。

时间限制：$2\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$

下载

样例数据下载