يعطيك 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$ مستحيل.