Trong Geometry Dash, các chướng ngại vật thường có thể được chia thành hai loại chướng ngại vật chính là gai nhọn và bức tường. Việc thiết kế chướng ngại vật được gọi là thiết kế hay nếu như các chướng ngại vật bức tường không được đặt cạnh nhau quá nhiều. Một màn chơi đương nhiên sẽ hay nếu như màn chơi ấy được thiết kế hay.

Hiểu được điều này, Tèo đã vẽ ra \(t\) kế hoạch kinh doanh và mỗi kế hoạch có dạng như sau: Với mỗi kế hoạch Tèo sẽ dùng số tiền \(n\) đô la ít ỏi của mình để mua \(n\) chướng ngại vật trong game nhằm thiết kế một màn chơi hay để sinh lời. Tèo chọn ra một số \(k\) phong thủy là số bức tường tối đa có thể được đặt cạnh nhau. Dựa trên số cách có thể thiết kế màn chơi mà Tèo quyết định có dùng phương án này hay không.

Yêu cầu: Với mỗi kế hoạch, bạn hãy giúp Tèo đếm số cách thiết kế màn chơi nhé.

Input

• Dòng đầu tiên chứa \(T\) \((T \leq 10\)).
• \(t\) dòng tiếp theo, mỗi dòng chứa hai số \(n\) và \(k\) \((1 \leq n \leq 10^{5}, 0 \leq k \leq \min(n, 20))\).

Output

• Gồm \(t\) dòng, dòng thứ \(i\) là kết quả của kế hoạch thứ \(i\), vì kết quả rất lớn nên chỉ cần in ra số dư của kết quả khi chia cho \(220220061\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \leq 20\).
• Subtask \(2\) (\(30\%\) số điểm): \(k \leq 1\).
• Subtask \(3\) (\(40\%\) số điểm): không có ràng buộc gì thêm.

Example

2
3 1
5 1

5
13