题目背景

回首往昔，碧空如洗，日暖风恬。
溪石深浅有致地错落在明澈似玉的梦枫溪里。
浣熊们水上跑酷的无限趣忆亦于此伊始……

题目描述

日升月落，春去秋来，梦枫溪石的高度千变万化。 爱思考的小浣熊 CleverRaccoon 想探寻这些溪石究竟能构成多少种不同的高度序列。

现有若干个长度为 $n$ 的非负整数列 $a$。

当 $n>1$ 时，$a_1,a_n$ 的取值为 $0\sim m$，其它数 $a_i$ 的取值为 $0\sim m-1$，其中 $2\leq i \leq n-1$。

当 $n=1$ 时，$a_1$ 的取值为 $0\sim m+1$。

定义：当且仅当 $\forall i\in\{1,2,\dots ,n\},a_i=b_i$ 或 $\forall i\in\{1,2,\dots ,n\},a_i=b_{n-i+1}$ 时，数列 $a,b$ 相同。

现给定 $n,m$，请求出最多有多少个不同的数列，答案对 $998244353$ 取模。

输入格式

本题包含多组测试数据。

第一行，输入一个正整数 $T$，表示数据组数。

接下来 $T$ 行，每行输入以空格间隔的 $2$ 个正整数 $n,m$，意义见题目描述。

输出格式

共 $T$ 行，对于每组数据，一行输出一个正整数，表示答案对 $998244353$ 取模的结果。

3
1 3
2 2
6 3

5
6
666

提示

解释 #1

当 $n=1,m=3$ 时，$a_i\in\{0,1,2,3,4\}$，共有 $5$ 种不同的高度序列。

当 $n=2,m=2$ 时，共有 $6$ 种不同的高度序列，详情如下：

数据范围

本题采用 Subtask 捆绑测试。

对于 $100\%$ 的数据，保证 $1\leq n\leq10^{18},1\leq m\leq10^9,1\leq T\leq10^6$。