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$ орындағы префикстік қосындыларды айтады; яғни сізге $s_{p_j} = v_j$ ($1 \le j \le m$) түріндегі $m$ шектеу берілген.

Барлық шектеулерді қанағаттандыратын массивтер санын $998\,244\,353$ модулі бойынша есептеңіз. Егер ешбір массив барлық шектеулерді қанағаттандырмаса, жауап $0$ болады.

Кіріс деректер

Бірінші жолда тест жағдайларының санын білдіретін бүтін сан $T$ ($1 \le T \le 10^4$) берілген. Одан кейін тест жағдайларының сипаттамасы беріледі.

Әрбір тест жағдайы келесідей беріледі:

Бірінші жолда сәйкесінше массивтің ұзындығын және префикстік қосынды шектеулерінің санын білдіретін екі бүтін сан $n$ және $m$ ($1 \le n \le 100$, $0 \le m \le n$) берілген.

Келесі $m$ жолдың $j$-ші жолында екі бүтін сан $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$ шектеуі мүмкін емес.