310682: CF1869E. Travel Plan

E. Travel Plantime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

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.

Input

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

Output

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

ExampleInput

5
3 1
2 2
10 9
43 20
154 147

Output

6
19
583217643
68816635
714002110

Note

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

题目大意：
在高考后的暑假，汤姆和丹尼尔计划去旅行。他们的国家有n个城市，编号从1到n。每个城市i（1≤i≤n）有以下两条路：
- 如果2i≤n，则有一条路连接城市i和2i；
- 如果2i+1≤n，则有一条路连接城市i和2i+1。
丹尼尔为每个城市选择一个介于1和m之间的整数值，记为ai。定义si,j为城市i和j之间简单路径上的城市最大值。旅行计划的分数是所有可能的si,j之和。汤姆想要知道所有可能的旅行计划的总分数。你需要帮助丹尼尔找到这个值，结果对998,244,353取模。

输入输出数据格式：
输入：
- 第一行包含一个整数t（1≤t≤200），表示测试用例的数量。
- 每个测试用例包含一行，有两个整数n和m（1≤n≤10^18，1≤m≤10^5），分别表示城市的数量和城市的最大值。
- 所有测试用例的m之和不超过10^5。

输出：
- 对于每个测试用例，输出一个整数，表示所有可能的旅行计划的总分数，结果对998,244,353取模。

示例：
输入：
5
3 1
2 2
10 9
43 20
154 147

输出：
6
19
583217643
68816635
714002110题目大意： 在高考后的暑假，汤姆和丹尼尔计划去旅行。他们的国家有n个城市，编号从1到n。每个城市i（1≤i≤n）有以下两条路： - 如果2i≤n，则有一条路连接城市i和2i； - 如果2i+1≤n，则有一条路连接城市i和2i+1。 丹尼尔为每个城市选择一个介于1和m之间的整数值，记为ai。定义si,j为城市i和j之间简单路径上的城市最大值。旅行计划的分数是所有可能的si,j之和。汤姆想要知道所有可能的旅行计划的总分数。你需要帮助丹尼尔找到这个值，结果对998,244,353取模。 输入输出数据格式： 输入： - 第一行包含一个整数t（1≤t≤200），表示测试用例的数量。 - 每个测试用例包含一行，有两个整数n和m（1≤n≤10^18，1≤m≤10^5），分别表示城市的数量和城市的最大值。 - 所有测试用例的m之和不超过10^5。 输出： - 对于每个测试用例，输出一个整数，表示所有可能的旅行计划的总分数，结果对998,244,353取模。 示例： 输入： 5 3 1 2 2 10 9 43 20 154 147 输出： 6 19 583217643 68816635 714002110