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$ הוא בלתי אפשרי.