Đường đi trên lưới

Cho một lưới ô vuông gồm \(r\) hàng và \(c\) cột. Các hàng được đánh số từ \(1\) tới \(r\) theo thứ tự từ trên xuống dưới, các cột được đánh số từ \(1\) tới \(c\) theo thứ tự từ trái qua phải. Ô ở hàng \(x\) và cột \(y\) được kí hiệu là ô \((x, y)\).

Xuất phát từ góc trái trên \((1, 1)\), bạn cần đi xuống góc phải dưới \((r, c)\). Ở mỗi bước, bạn được di chuyển từ vị trí hiện tại (giả sử là ô \((x, y)\)) một bước theo một trong ba hướng: sang phải (sang ô \((x, y + 1)\)), xuống dưới (sang ô \((x + 1, y)\)) hoặc chéo xuống (sang ô \((x + 1, y + 1)\)), như hình minh họa dưới đây:

\begincenter

\endcenter

Bạn được cho \(q\) câu hỏi, mỗi câu hỏi gồm hai số \(r\) và \(c\). Hãy đếm số cách đi từ ô \((1, 1)\) tới ô \((r, c)\) ở từng câu hỏi. Do kết quả có thể rất lớn, bạn chỉ cần in ra đáp số theo modulo \(998244353\).

Input

Dòng đầu tiên chứa số nguyên \(q\) \((1 \leq q \leq 10^5)\) cho biết số câu hỏi.

\(q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(r\) và \(c\) \((1 \leq r, c \leq 2300)\) thể hiện một câu hỏi.

Output

Với mỗi câu hỏi, in ra một số nguyên là số cách đi từ ô \((1, 1)\) đến ô \((r, c)\) modulo \(998244353\).

Example

2
2 2
3 3

3 13 

Scoring

• Subtask \(1\) (\(33\) điểm): \(q = 1\) và \(r, c \leq 10\)

• Subtask \(2\) (\(17\) điểm): \(q \leq 10^5\) và \(r, c \leq 10\)

• Subtask \(3\) (\(30\) điểm): \(q = 1\) và \(r, c \leq 2300\)

• Subtask \(4\) (\(20\) điểm): \(q \leq 10^5\) và \(r, c \leq 2300\)