VegiCat cho bạn hai số nguyên $n$ và $m$. Xét các mảng số nguyên $a_1, a_2, \ldots, a_n$ sao cho

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

Đặt $s_i = a_1 + a_2 + \ldots + a_i$ là các tổng tiền tố của $a$. VegiCat cũng cho bạn biết các tổng tiền tố tại $m$ vị trí; nghĩa là bạn được cho $m$ ràng buộc có dạng $s_{p_j} = v_j$ ($1 \le j \le m$).

Hãy đếm số lượng mảng thỏa mãn tất cả các ràng buộc, chia lấy dư cho $998\,244\,353$. Nếu không có mảng nào thỏa mãn tất cả các ràng buộc, đáp án là $0$.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $T$ ($1 \le T \le 10^4$), là số lượng bộ dữ liệu. Mô tả của các bộ dữ liệu theo sau.

Mỗi bộ dữ liệu được cho như sau:

Dòng đầu tiên chứa hai số nguyên $n$ và $m$ ($1 \le n \le 100$, $0 \le m \le n$), lần lượt là độ dài của mảng và số lượng ràng buộc tổng tiền tố.

Dòng thứ $j$ trong $m$ dòng tiếp theo chứa hai số nguyên $p_j$ và $v_j$ ($1 \le p_j \le n$, $0 \le v_j \le 10^9$). Dòng này mô tả một ràng buộc: tổng của $p_j$ phần tử đầu tiên của mảng phải bằng $v_j$.

Các vị trí $p_j$ được cho theo thứ tự tăng dần nghiêm ngặt.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một số nguyên — số lượng mảng hợp lệ chia lấy dư cho $998\,244\,353$.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

1
1
2
2
2
0

Ghi chú

Nếu không có bất kỳ ràng buộc tiền tố nào thì có đúng $2^{n-1}$ mảng như vậy, bởi vì mỗi hiệu trong số $n - 1$ hiệu của hai phần tử kề nhau có thể độc lập nhận giá trị $0$ hoặc $1$.

Trong bộ dữ liệu thứ hai, mảng duy nhất có $s_3 = 1$ là $(0, 0, 1)$.

Trong bộ dữ liệu thứ ba, $s_2 = 0$ buộc $a_2 = 0$, sau đó $a_3$ có thể là $0$ hoặc $1$.

Trong bộ dữ liệu thứ tư, các mảng thỏa mãn là $(0, 1, 1, 1)$ và $(0, 0, 1, 2)$.

Trong bộ dữ liệu thứ năm, các mảng có $s_5 = 4$ là $(0, 0, 1, 1, 2)$ và $(0, 1, 1, 1, 1)$.

Trong bộ dữ liệu thứ sáu, $s_2 = 0$ buộc $a_1 = a_2 = 0$, do đó $s_5 \le 6$. Ràng buộc $s_5 = 10$ là không thể thỏa mãn.