Pleasant Permutations

A sequence of n integers is called a permutation if it contains all integers from 1 to n exactly once. A permutation p1, p2, ..., pn, is called pleasant if it has no two consecutive elements that differ by d.

In other words, $ \left| p_i - p_{i+1} \right| \neq d $ for 1 ≤ i ≤ n-1.

You are given n and d, you have to find the number of pleasant permutations. Since this number can be large, you have to output it modulo 998244353.

Input

The first line of input contains a single integer t (1 ≤ t ≤ 100 — the number of test cases.

Each of the following t lines, contains two integers, n (2 ≤ n ≤ 106) and d ($\frac{n}{2}$ ≤ d ≤ n).

Output

For each case, output a single integer, the number of pleasant permutations modulo 998244353.

Sample

Input	Output
4 2 1 3 2 3 3 10 7	0 2 6 1895040