Description

Beads of red, blue or green colors are connected together into a circular necklace of $n$ beads. If the repetitions that are produced by rotation around the center of the circular necklace are all neglected, the green beads appear no more than $k$ times, and all adjacent beads are of different colors, how many different forms of the necklace are there?

Format

Input

The first line contains an integer $T(1≤T≤10)$representing the number of test cases.

For each test case, there are two integers $n,k(3≤n≤10^6,0≤k≤10^6)$in one line.

It is guaranteed that $∑n,∑k<5∗10^6$.

Output

For each test case, print a line with an integer, representing the answer, modulo $998244353$.

Samples

3
3 1
4 1
10 3

2
3
58