题目描述

Solve the problem below for $T$ test cases.

You are given two integers $M$ and $D$. You are interested in a rooted weighted tree with the following conditions.

• Each edge has a weight of a positive integer.
• For each vertex $v$ of the tree, there exists $\textbf{no}$ set of $v$'s children of size $\textbf{strictly greater}$ than $M$ such that all the edges connecting $v$ and this set of children all have the same weight.
• The diameter of the tree is not greater than $D$. The diameter of a tree is the maximum distance between any two vertices.

Find the maximum number of vertices of such a tree. As the number of vertices can be very large, find the vertex count modulo $998\;244\;353$.

输入格式

The first line contains an integer $T$ ($1 \leq T \leq 100$), the number of test cases.

Each of the next $T$ lines contains two integers $M$ and $D$ ($1 \leq M, D \leq 10^9$) representing a case you have to solve.

输出格式

For each of the $T$ test cases, output a single line containing the maximum number of vertices modulo $998\;244\;353$.

3
2 4
165 1
20 20

12
2
891869870

提示

$\textit{Explanation of Sample 1:}$ The following illustrates, for the first case, a rooted tree with the maximum number of vertices.

:::align{center} :::