VegiCat vous donne deux entiers $n$ et $m$. Considérons les tableaux d'entiers $a_1, a_2, \ldots, a_n$ tels que

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

Soit $s_i = a_1 + a_2 + \ldots + a_i$ la somme préfixe de $a$. VegiCat vous indique également les sommes préfixes à $m$ positions ; autrement dit, on vous donne $m$ contraintes de la forme $s_{p_j} = v_j$ ($1 \le j \le m$).

Comptez le nombre de tableaux satisfaisant toutes les contraintes, modulo $998\,244\,353$. Si aucun tableau ne satisfait toutes les contraintes, la réponse est $0$.

Entrée

La première ligne contient un entier $T$ ($1 \le T \le 10^4$), le nombre de cas de test. La description des cas de test suit.

Chaque cas de test est donné comme suit :

La première ligne contient deux entiers $n$ et $m$ ($1 \le n \le 100$, $0 \le m \le n$), représentant respectivement la longueur du tableau et le nombre de contraintes de sommes préfixes.

La $j$-ième des $m$ lignes suivantes contient deux entiers $p_j$ et $v_j$ ($1 \le p_j \le n$, $0 \le v_j \le 10^9$). Cela décrit une contrainte : la somme des $p_j$ premiers éléments du tableau doit être égale à $v_j$.

Les positions $p_j$ sont données dans l'ordre strictement croissant.

Sortie

Pour chaque cas de test, affichez un entier — le nombre de tableaux valides modulo $998\,244\,353$.

Exemples

Entrée 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

Sortie 1

1
1
2
2
2
0

Remarque

Sans aucune contrainte de préfixe, il existe exactement $2^{n-1}$ tableaux de ce type, car chacune des $n - 1$ différences adjacentes peut valoir indépendamment $0$ ou $1$.

Dans le deuxième cas de test, le seul tableau vérifiant $s_3 = 1$ est $(0, 0, 1)$.

Dans le troisième cas de test, $s_2 = 0$ impose $a_2 = 0$, après quoi $a_3$ peut valoir $0$ ou $1$.

Dans le quatrième cas de test, les tableaux sont $(0, 1, 1, 1)$ et $(0, 0, 1, 2)$.

Dans le cinquième cas de test, les tableaux vérifiant $s_5 = 4$ sont $(0, 0, 1, 1, 2)$ et $(0, 1, 1, 1, 1)$.

Dans le sixième cas de test, $s_2 = 0$ impose $a_1 = a_2 = 0$, donc $s_5 \le 6$. La contrainte $s_5 = 10$ est impossible.