Necklace of Beads

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?

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\).

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

2021“MINIEYE杯”中国大学生算法设计超级联赛（1）