科学家们发现了一种繁殖方式很奇特的细菌。当一个房间里有 $x$ 个细菌时，每分钟它们会进行一次心灵感应，随后其中一个细菌会被选中进行分裂。每个特定细菌被选中的概率均为 $1/x$。

科学家们对这种分裂策略的平衡性很感兴趣。他们在房间里放置了 $n$ 个培养皿，每个培养皿中最初恰好有 $1$ 个细菌。在每次分裂后，系数 $d$ 的计算方式如下：如果其中一个培养皿中的细菌数量超过了其余所有培养皿中细菌数量之和，则 $d$ 被设为这两个数量之差。否则，$d$ 被设为 $0$。形式化地，如果培养皿中的细菌数量为 $a_1 \ge a_2 \ge \dots \ge a_n$，则 $d = \max(a_1 - a_2 - \dots - a_n, 0)$。

求研究过程中第 $1, 2, \dots, k$ 分钟后 $d$ 的值的总和的期望值。答案可以写成 $\frac{p}{q}$ 的形式，其中 $p$ 和 $q$ 是互质的整数，且 $q \not\equiv 0 \pmod{998\,244\,353}$。请输出一个整数 $r$，满足 $r \cdot q \equiv p \pmod{998\,244\,353}$。

输入格式

第一行包含一个整数 $t$，表示测试用例的数量 ($1 \le t \le 3 \cdot 10^5$)。

接下来的 $t$ 行，每行描述一个测试用例，包含两个整数 $n$ 和 $k$ ($1 \le n, k \le 10^6$)。

保证所有测试用例中 $n$ 的总和与 $k$ 的总和均不超过 $2 \cdot 10^6$。

输出格式

对于每个测试用例，输出一行，包含一个整数 $r$，满足 $r \cdot q \equiv p \pmod{998\,244\,353}$，其中 $\frac{p}{q}$ 是研究过程中第 $1, 2, \dots, k$ 分钟后 $d$ 的值的总和的期望值。

样例

输入 1

8
1 1
1 2
2 1
2 2
3 1
3 2
3 3
4 3

输出 1

2
5
1
332748120
0
499122177
299473307
598946612