农夫 Nhoj 带着他的奶牛来到农夫约翰的农场玩游戏! FJ 的农场可以通过一条数轴进行建模,其中墙位于点 $$$0$$$ 和 $$$l + 1$$$ 处。农场里有 $$$2n$$$ 头奶牛,其中 $$$n$$$ 属于 FJ,其余 $$$n$$$ 属于 FN。他们将每头奶牛放置在不同的点,FJ 的奶牛和 FN 的奶牛都不会相邻。如果两头牛之间没有其他牛,则它们是相邻的。
形式上,如果 $$$a_1, a_2, \ldots, a_n$$$ 代表 FJ 的奶牛的位置,而 $$$b_1, b_2, \ldots, b_n$$$ 代表 FN 的奶牛的位置,则 $$$0 < a_1 < b_1 < a_2 < b_2 < \ldots < a_n < b_n < l + 1$$$ 或 $$$0 < b_1 < a_1 < b_2 < a_2 < \ldots < b_n < a_n < l + 1$$$。
在一步操作中,农民选择一个数字 $$$k$$$ $$$(1 \leq k \leq n)$$$ 和一个方向(左或右)。然后,该农民选择他的 $$$k$$$ 头奶牛,并将它们朝着所选方向移动一个位置。农民不能将他的任何牛移到墙上或另一个农民的牛身上。如果一个农民不能移动任何奶牛,那么这个农民就输了。 FJ 开始游戏,进行第一个回合。
给定 $$$l$$$ 和 $$$n$$$,找到如果两个农民都发挥最佳状态,Farmer John 可能获胜的游戏配置数量。游戏可能会无限期地继续下去,没有农民获胜。如果存在任何 $$$i$$$ 使得 $$$a_i$$$ 或 $$$b_i$$$ 不同,则配置与另一个配置不同。输出对 $$$998\,244\,353$$$ 取模的答案。
输入
第一行包含 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。
每个测试用例包含两个整数 $$$l$$$ 和 $$$n$$$ ($$$2 \leq l \leq 10^6, 1 \leq n \leq \lfloor \frac{l}{2} \rfloor$$$) - 数轴的长度和每个农民将放置的奶牛数量。
保证所有测试用例的$$$l$$$总和不超过$$$10^6$$$。
输出
对于每个测试用例,输出一个整数:如果两个农民都发挥最佳,则 Farmer John 获胜的游戏配置数量,以 $$$998\,244\,353$$$ 为模。
示例
输入 #1
3 2 1 3 1 420 69
输出 #1
0 2 870279412
注意
设 J 表示 FJ 的牛,N 表示 FN 的牛,_ 表示空白区域。
对于第一个测试用例,两种可能的配置是 JN 或 NJ。在这两种情况下,由于FJ都先回合并且无法做出任何动作,所以他无法获胜。
对于第二种情况,FJ 获胜有两种可能的配置:N_J 和 J_N。