CF1942E.Farm Game

Farm Game

Lunatic Princess - Touhou

FN 带着他的奶牛来到 FJ 的农场里玩游戏！FJ 的农场可视作一条 $0$ 点和 $l+1$ 点有墙的数轴。FJ 和 FN 各有 $n$ 头牛（共 $2n$ 头牛）。他们把他们的奶牛分别放到不同的整点上，并且 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 $。

对于一次移动，农夫（FJ 或 FN）选择一个整数 $ k $ $ (1 \leq k \leq n) $ 和一个方向（左或右）。然后他会选择 $ k $ 头他的牛向此方向移动一个单位。农夫不能将他的牛移到墙上或者另外一位农夫的牛上。如果有一人无法再移动他的牛，他就输了。FJ 先手。

给定 $ l $ 和 $ n $，找到在双方都采取最优策略下，FJ 赢的不同的初始奶牛排列数量。有可能游戏会无穷尽地继续下去，这时算作无人获胜。答案取模 $ 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 $。

对于每组测试数据输出一个整数：在双方都采取最优策略下，FJ 赢的不同的初始奶牛排列数量，答案模 $ 998,244,353 $。