Counting Peak Permutations

Rikka gives you \(T\) queries. For each query, you are given two positive integers \(n\) and \(k\). Your task is to count the number of permutations \(\pi = [\pi_1, \pi_2, \dots, \pi_n]\) of \(\{1, 2, \dots, n\}\) that 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}\).

Output the answer modulo \(998244353\).

inputFormat

The first line contains an integer \(T\), the number of test cases.

Each of the next \(T\) lines contains two integers \(n\) and \(k\).

outputFormat

For each test case, output the number of valid permutations that satisfy the conditions, modulo \(998244353\). Each answer should be printed on a separate line.

sample

1
3 1

2