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$ จึงเป็นไปไม่ได้