Cho một bảng có kích thước \(N×M\). Mỗi ô trong đó chứa một số nguyên dương. Từ ô \((x,y)\) chỉ có thể đi được đến ô \((x,y+1)\) hoặc ô \((x+1,y)\) hoặc \((x+1,y+1).\)

Yêu cầu: Cho \(q\) truy vấn, mỗi truy vấn gồm hai số \( u\) và \(v\). Hãy đếm số cách đi từ ô \((1,1)\) tới ô \((u,v)\) ở từng câu hỏi. In Kết quả modulo \(998244353\).

Input

• Dòng đầu tiên chứa hai số nguyên dương \(q(1≤q≤10^5 )\).

• \(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u,v (1≤u,v≤3000).\)

Output

• Ghi trên một dòng gồm q số, số thứ i số cách đi từ ô \((1,1)\) tới ô \((u,v)\) modulo \(998244353\) với truy vấn thứ \(i\) tương ứng.

Sample Input

2
2 2
3 3

Sample Output

3 13