Assassination Journey Happiness

Six assassins—Akaba Gou, Sugino Yuujin, Okuda Aimi, Kayano Kaede, Kanzaki Yukiko, and Shiota Nagisa—embark on an assassination trip in Kyoto, with the goal of sniping their teacher. At the same time, the government sends in a professional sniper known as "Crimson Eye." In order to maximize their happiness while accomplishing the mission, the clever Kanzaki Yukiko derived a surprising formula for happiness which depends on the number of attractions visited and the number of assassinations carried out.

Suppose the team visits n attractions and commits m assassinations. Define $$ \Gamma(a,b)=\begin{cases} 1, & \text{if }a>b,\\ \prod_{i=a}^b i, & \text{if }a\le b, \end{cases} $$ and let $$ A(i)=\sum_{j=0}^{i} \Bigl(\binom{i}{j}^2\,\binom{n+2i-j}{2i}\Bigr). $$ Then the happiness is defined as $$ H = \sum_{i=0}^{m} \left\{ \sqrt{A(i)} \times \frac{\Gamma(n-i+1, n)}{\Gamma(n+1, n+i)} \right\}. $$ It is guaranteed that each term $$ \frac{\sqrt{A(i)}}{\Gamma(n+1,n+i)} \times \Gamma(n-i+1,n) $$ is an integer. Since the answer could be very large, output it modulo 998244353.

You are given T test cases. For each test case, given integers n and m, compute the happiness H modulo 998244353.

inputFormat

The first line contains a single integer T, the number of test cases.

Each of the next T lines contains two integers n and m separated by a space.

outputFormat

For each test case, output one line containing the happiness modulo 998244353.

sample

3
1 1
2 1
3 2

2
3
7