CF1868C.Travel Plan

During the summer vacation after Zhongkao examination, Tom and Daniel are planning to go traveling.

There are $n$ cities in their country, numbered from $1$ to $n$. And the traffic system in the country is very special. For each city $i$ ($1 \le i \le n$), there is

• a road between city $i$ and $2i$, if $2i\le n$;
• a road between city $i$ and $2i+1$, if $2i+1\le n$.

Making a travel plan, Daniel chooses some integer value between $1$ and $m$ for each city, for the $i$-th city we denote it by $a_i$.

Let $s_{i,j}$ be the maximum value of cities in the simple$^\dagger$ path between cities $i$ and $j$. The score of the travel plan is $\sum_{i=1}^n\sum_{j=i}^n s_{i,j}$.

Tom wants to know the sum of scores of all possible travel plans. Daniel asks you to help him find it. You just need to tell him the answer modulo $998\,244\,353$.

$^\dagger$ A simple path between cities $x$ and $y$ is a path between them that passes through each city at most once.

中考结束后暑假期间，Tom 和 Daniel 计划外出旅行。

他们的国家共有 $n$ 座城市，编号从 $1$ 到 $n$。该国的交通系统非常特殊：对每座城市 $i$（$1 \le i \le n$），存在

• 一条连接城市 $i$ 与城市 $2i$ 的道路，当且仅当 $2i \le n$；
• 一条连接城市 $i$ 与城市 $2i+1$ 的道路，当且仅当 $2i+1 \le n$。

在制定旅行计划时，Daniel 为每座城市选择一个介于 $1$ 到 $m$ 之间的整数值；记第 $i$ 座城市的取值为 $a_i$。

令 $s_{i,j}$ 表示城市 $i$ 与城市 $j$ 之间简单路径$^\dagger$ 上所有城市中 $a_k$ 值的最大值。该旅行计划的得分为 $\sum_{i=1}^n\sum_{j=i}^n s_{i,j}$。

Tom 想知道所有可能旅行计划得分的总和。Daniel 请你帮他计算这个总和，你只需输出结果对 $998\,244\,353$ 取模后的值。

$^\dagger$ 城市 $x$ 与 $y$ 之间的简单路径是指一条连接二者、且至多经过每个城市一次的路径。

The first line of input contains a single integer $t$ ($1\le t\le 200$) — the number of test cases. The description of test cases follows.

The only line of each test case contains two integers $n$ and $m$ ($1\leq n\leq 10^{18}$, $1\leq m\leq 10^5$) — the number of the cities and the maximum value of a city.

It is guaranteed that the sum of $m$ over all test cases does not exceed $10^5$.

输入的第一行包含一个整数 $t$（$1\le t\le 200$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例仅一行，包含两个整数 $n$ 和 $m$（$1\leq n\leq 10^{18}$，$1\leq m\leq 10^5$），分别表示城市的数量以及城市值的最大值。

保证所有测试用例中 $m$ 的总和不超过 $10^5$。

For each test case output one integer — the sum of scores of all possible travel plans, modulo $998\,244\,353$.

对于每个测试用例，输出一个整数——所有可能旅行计划的得分之和对 $998\,244\,353$ 取模的结果。

In the first test case, there is only one possible travel plan:

Path $1\rightarrow 1$: $s_{1,1}=a_1=1$.

Path $1\rightarrow 2$: $s_{1,2}=\max(1,1)=1$.

Path $1\rightarrow 3$: $s_{1,3}=\max(1,1)=1$.

Path $2\rightarrow 2$: $s_{2,2}=a_2=1$.

Path $2\rightarrow 1\rightarrow 3$: $s_{2,3}=\max(1,1,1)=1$.

Path $3\rightarrow 3$: $s_{3,3}=a_3=1$.

The score is $1+1+1+1+1+1=6$.

In the second test case, there are four possible travel plans:

Score of plan $1$: $1+1+1=3$.

Score of plan $2$: $1+2+2=5$.

Score of plan $3$: $2+2+1=5$.

Score of plan $4$: $2+2+2=6$.

Therefore, the sum of score is $3+5+5+6=19$.

在第一个测试用例中，仅存在一种可能的旅行方案：

路径 $1\rightarrow 1$：$s_{1,1}=a_1=1$。

路径 $1\rightarrow 2$：$s_{1,2}=\max(1,1)=1$。

路径 $1\rightarrow 3$：$s_{1,3}=\max(1,1)=1$。

路径 $2\rightarrow 2$：$s_{2,2}=a_2=1$。

路径 $2\rightarrow 1\rightarrow 3$：$s_{2,3}=\max(1,1,1)=1$。

路径 $3\rightarrow 3$：$s_{3,3}=a_3=1$。

总得分为 $1+1+1+1+1+1=6$。

在第二个测试用例中，共有四种可能的旅行方案：

方案 $1$ 的得分：$1+1+1=3$。

方案 $2$ 的得分：$1+2+2=5$。

方案 $3$ 的得分：$2+2+1=5$。

方案 $4$ 的得分：$2+2+2=6$。

因此，所有方案得分之和为 $3+5+5+6=19$。