Background

All the members are thinking about organizing an anniversary event, but Xiao Xi only wants to slack off.

So Xiao Xi decided to do something big (go slack off in a big way).

Problem Description

Because Xiao Xi often slacks off, he is very popular among the slackers. Today, Xiao Xi decides to livestream on the most "degenerate" tree in the fish world.

This tree is very "degenerate". It has no root. It has $n$ nodes, labeled $1,2,\dots,n$, and there are $n - 1$ edges connecting them. It can change its form: edges may move, disappear, or grow. Let $k$ be the number of edges $(u,v)$ in the tree that satisfy $|u-v|=1$. Then the value of this form is $k \times c^k$.

Xiao Xi wants to introduce the value of the tree to the salted fish, but he only wants to slack off. So he asks you to compute the sum of the values over all different forms of the tree, and output it modulo $998244353$.

Multiple test cases.

Input Format

The first line contains a positive integer $T$, the number of test cases.
The next $T$ lines each contain a positive integer $n$ and a non-negative integer $c$, describing one test case.

Output Format

Output $T$ lines. The $i$-th line contains a non-negative integer, the answer for the $i$-th test case.

3
4 2
4 3
5 1

94
228
200

Hint

For $10\%$ of the testdata, $T = 1$, $n \le 10$.
For $30\%$ of the testdata, $T \le 10$, $n \le 300$.
For $70\%$ of the testdata, $T \le 10$, $n \le 10^6$.
For $100\%$ of the testdata, $1 \le T \le 10^5$, $1 \le n \le 10^{18}$, $1 \le c < 998244353$.

Translated by ChatGPT 5