VegiCat te da dos enteros $n$ y $m$. Considera los arreglos de enteros $a_1, a_2, \ldots, a_n$ tales que

$$ a_1 = 0, \qquad 0 \le a_{i+1} - a_i \le 1 \quad (1 \le i < n). $$

Sea $s_i = a_1 + a_2 + \ldots + a_i$ la suma prefija de $a$. VegiCat también te dice las sumas prefijas en $m$ posiciones; es decir, se te dan $m$ restricciones de la forma $s_{p_j} = v_j$ ($1 \le j \le m$).

Cuenta el número de arreglos que satisfacen todas las restricciones, módulo $998\,244\,353$. Si ningún arreglo satisface todas las restricciones, la respuesta es $0$.

Entrada

La primera línea contiene un entero $T$ ($1 \le T \le 10^4$), el número de casos de prueba. A continuación sigue la descripción de los casos de prueba.

Cada caso de prueba se da de la siguiente manera:

La primera línea contiene dos enteros $n$ y $m$ ($1 \le n \le 100$, $0 \le m \le n$), la longitud del arreglo y el número de restricciones de sumas prefijas, respectivamente.

La $j$-ésima de las siguientes $m$ líneas contiene dos enteros $p_j$ y $v_j$ ($1 \le p_j \le n$, $0 \le v_j \le 10^9$). Esto describe una restricción: la suma de los primeros $p_j$ elementos del arreglo debe ser igual a $v_j$.

Las posiciones $p_j$ se dan en orden estrictamente creciente.

Salida

Para cada caso de prueba, imprime un entero: el número de arreglos válidos módulo $998\,244\,353$.

Ejemplos

Entrada 1

6
1 0
3 1
3 1
3 1
2 0
4 1
4 3
5 2
1 0
5 4
5 2
2 0
5 10

Salida 1

1
1
2
2
2
0

Nota

Sin ninguna restricción de prefijos hay exactamente $2^{n-1}$ arreglos de este tipo, porque cada una de las $n - 1$ diferencias adyacentes puede ser independientemente $0$ o $1$.

En el segundo caso de prueba, el único arreglo con $s_3 = 1$ es $(0, 0, 1)$.

En el tercer caso de prueba, $s_2 = 0$ fuerza a que $a_2 = 0$, tras lo cual $a_3$ puede ser $0$ o $1$.

En el cuarto caso de prueba, los arreglos son $(0, 1, 1, 1)$ y $(0, 0, 1, 2)$.

En el quinto caso de prueba, los arreglos con $s_5 = 4$ son $(0, 0, 1, 1, 2)$ y $(0, 1, 1, 1, 1)$.

En el sexto caso de prueba, $s_2 = 0$ fuerza a que $a_1 = a_2 = 0$, por lo que $s_5 \le 6$. La restricción $s_5 = 10$ es imposible.