Permutations with Exact Peaks and Endpoint Conditions

Rikka gives you T test cases. In each test case, you are given two positive integers n and k. You are to count, modulo 998244353, the number of permutations \(\pi\) of \(\{1,2,\dots,n\}\) which satisfy the following conditions:

• \(\pi_1 < \pi_2\).
• \(\pi_{n-1} > \pi_{n}\).
• There are exactly \(k\) indices \(i\) (with \(2\le i\le n-1\)) such that \(\pi_{i-1} \pi_{i+1}\) (that is, \(\pi_i\) is a peak).

Note: This version differs from the original in that the range of some parameter (denoted by \(r\) in the original statement) has been extended. It is expected that an \(O(n\log^2n)\) divide-and-conquer FFT method might fail. If you have an FFT based solution that passes, please contact the problem setter. Also, if your solution is \(O(n\log n)\) be careful with constant‐factor optimizations.

The answer for each test case should be given modulo \(998244353\).

inputFormat

The first line contains a single integer T representing the number of test cases. Each of the following T lines contains two integers n and k separated by a space.

It is guaranteed that \(n\) is small (for example, \(n \le 8\)) so that a brute‐force solution can pass all the test cases.

outputFormat

For each test case, output a single line containing the count of valid permutations modulo \(998244353\).

sample

1
3 1

2