题目背景

团员们满脑子都是办周年庆，但小僖只想摸鱼。

于是小僖决定干一件大事（去摸一条大鱼）。

题目描述

小僖由于经常摸鱼，在摸鱼众中享有很高的人气。而今天小僖决定去鱼世界里最颓的树上直播。

这颗树非常颓，没有根，上面有 $n$ 个结点，每个结点从 $1,2,\dots,n$ 进行标号，还有 $n - 1$ 条边将它们连通。它会变换形态，边会移动、消失或生长。记 $k$ 为树中满足 $|u-v|=1$ 的边 $(u,v)$ 的数量，则该形态的价值为 $k \times c^k$ 。

小僖想要向咸鱼们介绍树的价值，他只想着摸鱼。所以他找到了你，要求你求出树所有不同形态的权值和，并将其对 $998244353$ 取模后输出。

多组数据。

输入格式

第一行，一个正整数 $T$，表示数据组数。
以下 $T$ 行，每行一个正整数 $n$ 和一个非负整数 $c$，表示一组数据。

输出格式

$T$ 行，第 $i$ 行一个非负整数，表示第 $i$ 组数据的答案。

3
4 2
4 3
5 1

94
228
200

提示

对于 $10\%$ 的数据，$T = 1$，$n \le 10$；
对于 $30\%$ 的数据，$T \le 10$，$n \le 300$；
对于 $70\%$ 的数据，$T \le 10$，$n \le 10^6$；
对于 $100\%$ 的数据，$1 \le T \le 10^5$，$1 \le n \le 10^{18}$，$1 \le c < 998244353$。