针对 $T$ 组测试数据求解该问题。

给定两个整数 $M$ 和 $D$。你需要构造一棵满足以下条件的有根加权树：

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

求满足上述条件的一棵树所能拥有的最大顶点数。由于顶点数可能非常大，请输出该数量对 $998\,244\,353$ 取模的结果。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。接下来的 $T$ 行，每行包含两个整数 $M$ 和 $D$ ($1 \le M, D \le 10^9$)，表示需要求解的一个测试用例。

输出格式

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

样例

输入 1

3
2 4
165 1
20 20

输出 1

12
2
891869870

说明 1

下图展示了第一个测试用例中，一棵拥有最大顶点数的有根树。

样例 1 的说明：下图展示了第一个测试用例中，一棵拥有最大顶点数的有根树。