F. 线段折叠

每测试点时间限制：$1$ 秒
每测试点内存限制：$1024$ MB

Peter 喜欢折叠线段。数轴上有一条线段，占据区间 $[\ell, r]$。现在到了折叠线段的黄金时间，Peter 决定小心地折叠这条线段。每一步中，只要可能，他会选择以下两种操作之一：

• 操作 LTR（从左向右折）：他将线段从左向右折叠，使得左端点 $\ell$ 与某个点 $x$（$\ell < x \le r$）重合，且 $\ell + x$ 是质数 *。
  Peter 选择此操作时，总是选择 最大的可能 $x$。
  注意折叠后，线段变为区间 $\left[ \frac{1}{2}(\ell + x),\; r \right]$。

• 操作 RTL（从右向左折）：他将线段从右向左折叠，使得右端点 $r$ 与某个点 $x$（$\ell \le x < r$）重合，且 $r + x$ 是质数。
  Peter 选择此操作时，总是选择 最小的可能 $x$。
  注意折叠后，线段变为区间 $\left[ \ell,\; \frac{1}{2}(r + x) \right]$。

折叠序列 指上述操作的一个序列。
Peter 希望经过若干次折叠后，得到 长度不能再缩短的区间，并且这个最终区间的长度在所有可能折叠方式中是最短的。
区间的长度定义为 $r - \ell$。

例如：初始区间 $[1,30]$，有以下三种折叠序列能得到最短的最终区间长度，如下图所示：（此处省略图）

请帮助 Peter 计算出 能得到最短最终区间长度的折叠序列 的数量。输出结果对 $998244353$ 取模。

*注：整数 $p > 1$ 是质数，如果不存在大于 $1$ 的整数 $a,b$ 使得 $p = ab$。

输入
第一行一个整数 $t$，表示测试用例数量。
接下来 $t$ 行，每行两个整数 $\ell$ 和 $r$。

数据范围：

• $1 \le t \le 10$
• $1 \le \ell < r \le 10^{12}$
• $r - \ell \le 10^5$

输出
对于每个测试用例，输出一行，表示能获得最短最终区间长度的折叠序列数量，对 $998244353$ 取模。

样例

输入：

3
1 30
16 18
142857 240135

输出：

3
1
63