题目描述

西西酱正在上化学实验课，实验室共有 $N$ 种药品，编号从 1 到 $N$。 今天，她想挑战将最多的药品混合在一起，制作成试剂。 当然药品尝试可是很危险的，据可靠消息，如果两种药品的编号差值恰好为 $D$，同时存在于试剂中就会立刻产生剧烈的爆炸。 而实验室生存守则亦有相关规定：“实验室放辣，禁闭室报道。” 因此，一旦引起爆炸，西西酱就得立刻结束实验，光速跑路。当然，如果药品全部加完也没有引起爆炸，则同样会结束实验。 西西酱想知道，在实验结束时，她最多有可能向试剂中加入多少种不同的药品。 特别的，当 $N$ 为奇数时西西酱还想知道，要加入尽量多种类的药品，共有多少种可能的加入次序，答案可能很大，输出答案对 998244353 取模的结果。

注意： 往实验中按 1, 2, 3 加入与按 1, 3, 2 加入视为不同的加入次序。

输入格式

第一行一个整数 $T$，表示数据组数。 对于每组数据，仅包含一行两个整数 $N, D$，表示药品的数量以及药品的反应性质。

输出格式

对于每组数据，输出一行。 若 $N$ 为偶数，则输出一个整数，最多能加入试剂的药品种类数。 若 $N$ 为奇数，则输出两个整数，最多能加入试剂的药品种类数，以及加入尽量多种类药品的前提下，加入次序方案数对 998244353 取模的结果。

样例

输入数据 1

7
5 1
5 2
19 3
123 4
123 122
123 123
198221 180

输出数据 1

4 12
4 24
11 522547200
64 304095868
123 770725334
123 482123450
99181 142798491

样例说明

对于第三组数据 (5 1)，一种最优策略是先加入 1, 3, 5，再加入 2 或 4。最终加入了 4 种试剂，共有 12 不同的次序。

数据范围与提示

所有测试数据的范围和特点如下表所示：

对于所有测试点，保证 $1 \le T \le 10, 1 \le N \le 10^6, 1 \le D \le 10^6$。