题目描述

塞格门特树是 Le Cheval 最喜欢的数据结构，它能高效地解决许多实际问题。

对于一个正整数 $n$，Le Cheval 构建出一棵下标属于整数区间 $[1,n]$ 的塞格门特树：

• 初始塞格门特树只有一个节点 $[1,n]$。
• 对于节点 $[l,r]$，若 $l<r$，则令 $mid=\lfloor \frac{l+r}{2}\rfloor$，Le Cheval 对这个节点建出两个子节点 $[l,mid]$ 与 $[mid+1,r]$。

Le Cheval 定义一个区间 $[l,r]$ 的区间定位为：尽可能少的区间互不相交的塞格门特树节点，使得它们区间的并集恰好是 $[l,r]$。

定义 $S_{[l,r]}$ 为 $[l,r]$ 的区间定位得到的点集，$U$ 为塞格门特树点集的全集。

你需要求出一个由 $[1,n]$ 的子区间构成的集合 $T$，满足 $\bigcup\limits_{[l,r]\in T} S_{[l,r]}=U$，同时最小化 $|T|$，称 $f_i$ 为 $n=i$ 时的 $|T|$，你需要求出 $(\sum_{i=l}^rf_i)\bmod353442899$。

输入格式

第一行，一个正整数 $q$，代表测试数据组数。

后 $q$ 行，每行两个正整数 $l,r$。

输出格式

共 $q$ 行，第 $i$ 行一个数代表第 $i$ 组测试数据的答案。

10
1 1
2 2
3 3
4 6
1 16
4 144
9 169
844 4997
114514 1919810
844844844844 1145141919810

1
3
4
18
132
6867
9359
6981925
72867217
151410714

提示

【数据范围】

对于 $100\%$ 的数据， $1 \le q \le 10^5$，$1 \le l \le r \le 10^{18}$。

特殊性质 A：保证 $l=r$。

特殊性质 B：保证 $r$ 是 $2$ 的幂。