311157: CF1942E. Farm Game

E. Farm Gametime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputLunatic Princess - Touhou⠀

Farmer Nhoj has brought his cows over to Farmer John's farm to play a game! FJ's farm can be modeled by a number line with walls at points $0$ and $l + 1$. On the farm, there are $2n$ cows, with $n$ of the cows belonging to FJ and the other $n$ belonging to FN. They place each of their cows at a distinct point, and no two FJ's cows nor FN's cows are adjacent. Two cows are adjacent if there are no other cows between them.

Formally, if $a_1, a_2, \ldots, a_n$ represents the positions of FJ's cows and $b_1, b_2, \ldots, b_n$ represents the positions of FN's cows, then either $0 < a_1 < b_1 < a_2 < b_2 < \ldots < a_n < b_n < l + 1$ or $0 < b_1 < a_1 < b_2 < a_2 < \ldots < b_n < a_n < l + 1$.

In one move, a farmer chooses a number $k$ $(1 \leq k \leq n)$ and a direction (left or right). Then, that farmer chooses $k$ of his cows and moves them one position towards the chosen direction. A farmer cannot move any of his cows onto the walls or onto another farmer's cow. If a farmer cannot move any cows, then that farmer loses. FJ starts the game, making the first turn.

Given $l$ and $n$, find the number of possible game configurations for Farmer John to win if both farmers play optimally. It may be the case that the game will continue indefinitely, in which no farmer wins. A configuration is different from another if there is any $i$ such that $a_i$ or $b_i$ is different. Output the answer modulo $998\,244\,353$.

Input

The first line contains $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

Each test case contains two integers $l$ and $n$ ($2 \leq l \leq 10^6, 1 \leq n \leq \lfloor \frac{l}{2} \rfloor$) — the length of the number line and the number of cows each farmer will place.

It is guaranteed the sum of $l$ over all test cases does not exceed $10^6$.

Output

For each test case output an integer: the number of game configurations where Farmer John wins if both farmers play optimally, modulo $998\,244\,353$.

ExampleInput

3
2 1
3 1
420 69

Output

0
2
870279412

Note

Let J denote FJ's cow, N denote FN's cow, and _ denote an empty space.

For the first test case, the two possible configurations are JN or NJ. In both cases, since FJ makes the first turn and cannot make any moves, he cannot win.

For the second case there are two possible configurations for FJ to win: N_J and J_N.

**题目大意：**

农夫Nhoj带着他的牛到农夫John的农场玩游戏。农场可以由一条数轴表示，数轴上有0和\(l+1\)两堵墙。农场上共有\(2n\)头牛，其中\(n\)头属于John，另外\(n\)头属于Nhoj。他们把各自的牛放在不同的点上，且没有两头John的牛或两头Nhoj的牛相邻。如果用\(a_1, a_2, \ldots, a_n\)表示John的牛的位置，\(b_1, b_2, \ldots, b_n\)表示Nhoj的牛的位置，那么它们的位置关系要么是\(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\)头牛向选定的方向移动一格。农夫不能将任何牛移动到墙上或另一个农夫的牛上。如果一个农夫不能移动任何牛，那么他就输了。John先开始游戏。

给定\(l\)和\(n\)，求如果两个农夫都采取最优策略，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\)。

**输出数据格式：**

对于每个测试用例输出一个整数：如果两个农夫都采取最优策略，John赢的游戏配置数，对\(998,244,353\)取模。**题目大意：** 农夫Nhoj带着他的牛到农夫John的农场玩游戏。农场可以由一条数轴表示，数轴上有0和\(l+1\)两堵墙。农场上共有\(2n\)头牛，其中\(n\)头属于John，另外\(n\)头属于Nhoj。他们把各自的牛放在不同的点上，且没有两头John的牛或两头Nhoj的牛相邻。如果用\(a_1, a_2, \ldots, a_n\)表示John的牛的位置，\(b_1, b_2, \ldots, b_n\)表示Nhoj的牛的位置，那么它们的位置关系要么是\(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\)头牛向选定的方向移动一格。农夫不能将任何牛移动到墙上或另一个农夫的牛上。如果一个农夫不能移动任何牛，那么他就输了。John先开始游戏。 给定\(l\)和\(n\)，求如果两个农夫都采取最优策略，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\)。 **输出数据格式：** 对于每个测试用例输出一个整数：如果两个农夫都采取最优策略，John赢的游戏配置数，对\(998,244,353\)取模。