说明

对于 $T$ 组测试数据，解决以下问题。

给定两个整数 $M$ 和 $D$。你需要考虑一棵满足以下条件的带权有根树。

• 每条边的权重均为正整数。
• 对于树中的每个顶点 $v$，不存在一个大小严格大于 $M$ 的 $v$ 的子节点集合，使得连接 $v$ 与该子节点集合中所有节点的边都具有相同的权重。
• 树的直径不超过 $D$。树的直径定义为任意两个顶点之间的最大距离。

求满足条件的树的最大顶点数。由于顶点数可能非常大，请输出顶点数对 $998\;244\;353$ 取模的结果。

输入格式

第一行包含一个整数 $T$（$1 \leq T \leq 100$），表示测试数据的组数。

接下来的 $T$ 行，每行包含两个整数 $M$ 和 $D$（$1 \leq M, D \leq 10^9$），表示一组需要求解的数据。

输出格式

对于每组测试数据，输出一行，包含最大顶点数对 $998\;244\;353$ 取模的结果。

3
2 4
165 1
20 20

12
2
891869870

提示

样例 1 解释： 下图展示了第一组数据中顶点数最多的有根树。

:::align{center} :::

翻译由 DeepSeek V3.2 完成