VegiCat дає вам два цілі числа $n$ і $m$. Розглянемо цілочисельні масиви $a_1, a_2, \ldots, a_n$, такі що

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

Нехай $s_i = a_1 + a_2 + \ldots + a_i$ — префіксні суми масиву $a$. VegiCat також повідомляє вам префіксні суми в $m$ позиціях; тобто вам задано $m$ обмежень вигляду $s_{p_j} = v_j$ ($1 \le j \le m$).

Порахуйте кількість масивів, що задовольняють усі обмеження, за модулем $998\,244\,353$. Якщо жоден масив не задовольняє всі обмеження, відповідь дорівнює $0$.

Вхідні дані

Перший рядок містить ціле число $T$ ($1 \le T \le 10^4$) — кількість наборів тестових даних. Далі йде опис наборів тестових даних.

Кожен набір тестових даних задається так:

Перший рядок містить два цілі числа $n$ і $m$ ($1 \le n \le 100$, $0 \le m \le n$) — довжину масиву та кількість обмежень на префіксні суми відповідно.

$j$-й із наступних $m$ рядків містить два цілі числа $p_j$ та $v_j$ ($1 \le p_j \le n$, $0 \le v_j \le 10^9$). Це описує обмеження: сума перших $p_j$ елементів масиву повинна дорівнювати $v_j$.

Позиції $p_j$ задані в порядку строгого зростання.

Вихідні дані

Для кожного набору тестових даних виведіть одне ціле число — кількість коректних масивів за модулем $998\,244\,353$.

Приклади

Вхідні дані 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

Вихідні дані 1

1
1
2
2
2
0

Примітка

Без жодних префіксних обмежень існує рівно $2^{n-1}$ таких масивів, оскільки кожна з $n - 1$ сусідніх різниць може незалежно дорівнювати $0$ або $1$.

У другому наборі тестових даних єдиний масив із $s_3 = 1$ — це $(0, 0, 1)$.

У третьому наборі тестових даних умова $s_2 = 0$ змушує $a_2 = 0$, після чого $a_3$ може дорівнювати $0$ або $1$.

У четвертому наборі тестових даних шуканими масивами є $(0, 1, 1, 1)$ та $(0, 0, 1, 2)$.

У п'ятому наборі тестових даних масивами з $s_5 = 4$ є $(0, 0, 1, 1, 2)$ та $(0, 1, 1, 1, 1)$.

У шостому наборі тестових даних умова $s_2 = 0$ змушує $a_1 = a_2 = 0$, тому $s_5 \le 6$. Обмеження $s_5 = 10$ є неможливим.