题目描述

你有 $n$ 个候选物品，你想要从中选出 $m$ 个物品放进体积为 $v$ 的背包里。

在选择物品时，你发现这些候选物品的体积分别为 $1, 2, \cdots, n$，于是你想知道有多少种选法可以恰好将体积为 $v$ 的背包填满。

注意，两种选法不同当且仅当存在至少一个候选物品只在某一种选法中被选择。

为了便于输出，我们假设从这样的 $n$ 个候选物品里选出 $m$ 个物品填满体积为 $v$ 的背包有 $f(v)$ 种选法，并令 $p$ 为使得 $f(p)$ 不为 $0$ 的最大正整数，你只需要输出 $\left(\sum\limits_{v = 1}^{p}{{19190506}^{p - v} f(v)}\right) \bmod 998244353$ 的值即可。显而易见的是当 $1 \leq m \leq n$ 时一定存在这样的 $p$。

输入格式

第一行包含一个正整数 $T$，表示有 $T$ 组测试数据。

接下来依次给出每组测试数据，每组测试数据仅两行，包含两个正整数 $n$ 和 $m$，含义如题目所示。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示题目中要求输出的值。

样例 1

input

1
3 2

output

238284724

对于该组样例，$f(3) = 1, f(4) = 1, f(5) = 1$，其他 $f(v)$ 都为 $0$，所以有 $p = 5$。

样例 2

input

1
4 2

output

186699913

对于该组样例，$f(3) = 1, f(4) = 1, f(5) = 2, f(6) = 1, f(7) = 1$，其他 $f(v)$ 都为 $0$，所以有 $p = 7$。

数据范围与提示

对于所有数据，$1 \leq T \leq 5 \times 10^5,$ $1 \leq m \leq n \leq 10^{12}$。