P15662 [ICPC 2025 Jakarta R] Maximeter

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$.

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