Monocarp 是一名珠宝商。最近，他收到了一份非常奇怪的订单——客户想要一套根据非常特定规则镶嵌宝石的金属圆盘。

每个圆盘由三种材料之一制成——铜、银或金。此外，每个圆盘被分为 $n$ 个扇区，按顺时针方向从 $1$ 到 $n$ 编号。这些扇区镶嵌有 $k$ 种类型的宝石：每个扇区要么恰好镶嵌一颗宝石，要么完全不镶嵌（在这种情况下，该扇区被称为空白扇区）。

如果满足以下条件，则称两个圆盘 $a$ 和 $b$ 具有相同的图案（ornament）：

• 对于圆盘 $a$ 的每个镶嵌有宝石的扇区 $i$，圆盘 $b$ 的扇区 $i$ 也镶嵌有相同类型的宝石，反之亦然。

如果两个圆盘由相同的材料制成且具有相同的图案，则称它们是相同的。

对于 Monocarp 将发送给客户的集合中的每个圆盘，他按以下方式制作：

• 首先，他为圆盘选择三种材料之一，并用该材料打造一个具有 $n$ 个空白扇区的圆盘；
• 然后，他用 $1$ 类宝石镶嵌圆盘的两个扇区。他镶嵌的第一个扇区可以是任意空白扇区；然而，第二个扇区总是顺时针方向的下一个空白扇区；
• 然后，他用 $2$ 类宝石镶嵌圆盘的两个扇区，以相同的方式选择它们；
• 然后，他用 $3$ 类宝石镶嵌圆盘的两个扇区，以相同的方式选择它们；
• 依此类推，直到对于 $k$ 种宝石中的每一种，都恰好有两个扇区镶嵌了该类型的宝石。圆盘中将恰好有 $n - 2k$ 个扇区保持空白。

例如，假设 $n = 5$，$k = 2$。制作圆盘的一种可能方式是：

• Monocarp 打造了一个具有 $n$ 个空白扇区的银质圆盘；
• 然后，他选择用 $1$ 类宝石镶嵌第 $4$ 个扇区。顺时针方向的下一个空白扇区是第 $5$ 个扇区，因此他也用 $1$ 类宝石镶嵌该扇区；
• 然后，他选择用 $2$ 类宝石镶嵌第 $3$ 个扇区。顺时针方向的下一个空白扇区是第 $1$ 个扇区（因为第 $4$ 和第 $5$ 个扇区都已被镶嵌），因此他也用 $2$ 类宝石镶嵌该扇区。

Monocarp 想要组装一个圆盘集合，使得：

• 集合中没有两个圆盘具有相同的图案（这也意味着集合中没有两个圆盘是相同的）；
• Monocarp 制作的圆盘数量是尽可能多的。

你的任务是计算 Monocarp 可以组装的不同集合的数量。当且仅当对于第一个集合中的每个圆盘，第二个集合中都有一个相同的圆盘，反之亦然时，两个集合才被认为是相同的。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 3 \cdot 10^5$）。

每个测试用例包含一行，包含两个整数 $n$ 和 $k$（$2 \le n \le 9 \cdot 10^8$；$1 \le k \le \frac{n}{2}$）。

输出格式

对于每个测试用例，输出一个整数——Monocarp 可以组装的不同集合的数量，模 $998\,244\,353$ 的结果。

样例

输入样例 1

8
4 1
4 2
5 2
10 2
10 4
10 5
1337 42
888888888 8

输出样例 1

81
81
14348907
412733925
572390210
572390210
359416572
358909282

说明

在第一个测试用例中，Monocarp 最多可以制作 $4$ 个圆盘：

• 具有图案 $[0, 0, 1, 1]$（其中 $0$ 表示空白扇区，$1$ 表示镶嵌有 $1$ 类宝石的扇区）；
• 具有图案 $[1, 0, 0, 1]$；
• 具有图案 $[0, 1, 1, 0]$；
• 具有图案 $[1, 1, 0, 0]$。

对于这些图案中的每一个，都有 $3$ 种选择材料的方式，因此答案为 $3^4 = 81$。

注意，图案 $[1, 0, 1, 0]$ 是不可能得到的：

• 如果 Monocarp 选择第 $1$ 个扇区并用 $1$ 类宝石镶嵌它，下一个空白扇区将是第 $2$ 个扇区，因此得到的图案将是 $[1, 1, 0, 0]$；
• 如果 Monocarp 选择第 $3$ 个扇区并用 $1$ 类宝石镶嵌它，下一个空白扇区将是第 $4$ 个扇区，因此得到的图案将是 $[0, 0, 1, 1]$。