中考结束后的暑假,汤姆和丹尼尔打算去旅行。
他们的国家/地区有 $$$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$$$ 路径中城市的最大值。出行计划的得分为$$$\sum_{i=1}^n\sum_{j=i}^n s_{i,j}$$$。
汤姆想知道所有可能的旅行计划的分数总和。丹尼尔请你帮他找到它。你只需要告诉他答案对 $$$998\,244\,353$$$ 取模即可。
$$$^\dagger$$$ 城市 $$$x$$$ 和 $$$y$$$ 之间的简单路径是它们之间最多经过每个城市一次的路径。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1\le t\le 200$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的唯一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1\leq n\leq 10^{18}$$$, $$$1\leq m\leq 10^5$$$) — 城市的数量和城市的最大值。
保证所有测试用例的 $$$m$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例,输出一个整数 - 所有可能的旅行计划的分数总和,以 $$$998\,244\,353$$$ 为模。
示例
输入 #1
5 3 1 2 2 10 9 43 20 154 147
输出 #1
6 19 583217643 68816635 714002110
注意
在第一个测试用例中,只有一个可能的旅行计划:
路径$$$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$$$。