I. Mental Abuse To Humans
time limit per test
4 s
memory limit per test
1024 megabytes
input
standard input
output
standard output

Bobo is asked to solve the following math problem:

Given $$$m$$$ pairs of integers $$$(x_1,t_1),(x_2,t_2),\ldots,(x_m,t_m)$$$ where $$$0 \leq x_i \lt n$$$ and $$$t_i\in \{0,1\}$$$, count the number of subsets $$$A \subseteq S_n=\{0,1,\dots,n-1\}$$$ satisfying

  • $$$\forall 1 \le i \le m$$$, $$$x_i \in A$$$ if and only if $$$t_i = 1$$$.
  • $$$ A +_n (S_n \setminus A) = S_n$$$.

For any two sets $$$A,B$$$ consisting of nonnegative integers, $$$A+_n B$$$ is defined by $$$$$$A+_n B = \{(a+b) \bmod n \mid a \in A, b \in B\}.$$$$$$

The answer might be enormous, and you should output the answer modulo $$$998\,244\,353$$$.

Input

Each test contains multiple test cases. The first line contains an integer $$$T$$$ ($$$1 \le T \le 5$$$) — the number of test cases. The following lines contain the description of each test case.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^{18}$$$, $$$0 \le m \le 5$$$), denoting the size of the universe and the number of integer pairs, respectively.

Then $$$m$$$ lines follow. The $$$i$$$-th line contains two integers $$$x_i,t_i$$$ ($$$0 \le x_i \lt n, t_i \in \{0,1\}$$$), describing the $$$i$$$-th integer pair.

It is guaranteed that $$$x_1,x_2,\ldots,x_m$$$ are pairwise distinct.

Output

For each test case, output a single integer, denoting the desired answer modulo $$$998\,244\,353$$$.

Example
Input
2
3 0
6 2
0 0
1 1
Output
0
4