和谐之树 · 改
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

在小马利亚的某一天，暮暮改造了和谐之树（相关定义见"D. 和谐之树"），并利用它给穗龙出题。
在小马利亚的另一天，根据白胡子星璇的魔法资料，暮暮发现......她还需要算出一个与她给穗龙出的题非常类似的问题。
现在暮暮每次会询问 ，穗龙需要求出所有对于满足 的正整数 k 建立 的和谐之树时，编号最大的节点编号之和。
特别的，由于答案较大，求出的和需要对 998244353 取模。

输入描述:

输入文件的第一行包含一个正整数 ，表示测试数据的数目。
每个测试数据占单独的一行，包含两个正整数 ，用空格隔开，表示询问区间。

输出描述:

对于每个测试数据，在单独的一行内输出取模后的结果。
示例1

输入

复制 
2
1 3
4 7

输出

复制 
9
42

说明

对于样例一，对区间 [1,1], [1,2], [1,3], [1,4], [1,5], [1,6], [1,7] 建立和谐之树时，编号最大的节点分别为 1, 3, 5, 7, 9, 13, 13.
对于询问 [1,3]，答案为 1+3+5=9；对于询问 [4,7]，答案为 7+9+13+13=42.