Problem 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?

Input

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

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

It is guaranteed that \(\sum n,\sum k < 5*10^6\).

Output

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

3
3 1
4 1
10 3

2
3
58