彼得喜欢折叠片段。数轴上有一段占据区间 $$$[\ell, r]$$$。由于现在是折叠片段的黄金时间,彼得决定小心翼翼地折叠片段。在每个步骤中,他都会尽可能选择以下两个操作之一:
1.操作$$$\tt{LTR}$$$:他从左向右折叠线段,其中$$$\ell$$$与点$$$x$$$ ($$$\ell < x \le r$$$)重合,使得$$$\ell+x$$$是素数$$$^{\text{*}}$$$。当Peter选择这个操作时,他总是选择最大的可能值$$$x$$$。请注意,该段之后占据区间 $$$[\frac{1}{2}(\ell+x), r]$$$。
2.操作$$$\tt{RTL}$$$:他将线段从右向左折叠,其中$$$r$$$与点$$$x$$$ ($$$\ell\le x < r$$$)重合,使得$$$r+x$$$是素数。当 Peter 选择此操作时,他总是选择尽可能小的值 $$$x$$$。请注意,该段之后占据区间 $$$[\ell, \frac{1}{2}(r+x)]$$$。
折叠序列是指上面指定的操作序列。 Peter 想要将线段折叠几次,从而得到尽可能短的间隔,并且其长度不能进一步减小。区间 $$$[\ell, r]$$$ 的长度自然定义为 $$$r-\ell$$$。让我们考虑以下示例。假设我们要折叠一个最初占据区间 $$$[1, 30]$$$ 的线段。共有三种折叠顺序,可得到最短的结果间隔,如下图所示。
请帮助 Peter 确定折叠序列的数量,以使所得间隔的长度尽可能短。输出对 $$$998244353$$$ 取模的数字。
输入
第一行包含一个整数$$$t$$$,表示测试用例的数量。在接下来的$$$t$$$ 行中,有两个整数$$$\ell$$$ 和$$$r$$$。
- $$$1 \let \le 10$$$
- $$$1 \le \ell < r \le 10^{12}$$$
- $$$r - \ell \le 10^5$$$
输出
对于每个测试用例,请输出一行,表示折叠给定线段的方式数量,以使生成的线段具有最短的可能长度,以 $$$998244353$$$ 为模。
示例
输入 #1
3 1 30 16 18 142857 240135
输出 #1
3 1 63