{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eBeads 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?\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains an integer \\( T(1\\le T\\le 10) \\)representing the number of test cases.\u003cbr\u003e\u003cbr\u003eFor each test case, there are two integers \\(n,k(3\\le n\\le 10^6,0\\le k\\le 10^6) \\)in one line.\u003cbr\u003e\u003cbr\u003eIt is guaranteed that \\(\\sum n,\\sum k \u0026lt; 5*10^6\\)."}},{"title":"Output","value":{"format":"HTML","content":"For each test case, print a line with an integer, representing the answer, modulo \\(998244353\\)."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n3 1\r\n4 1\r\n10 3\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n3\r\n58\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}