Peter 喜欢折叠线段。数轴上有一个占用了区间 $[\ell, r]$ 的线段。由于现在是折叠线段的黄金时期，Peter 决定仔细地折叠这条线段。在每一步中，只要可行，他就会选择以下两种操作之一：

1. 操作 LTR：他将线段从左向右折叠，使得 $\ell$ 与一个点 $x$（$\ell < x \le r$）重合，满足 $\ell + x$ 是一个素数*。当 Peter 选择此操作时，他总是选择尽可能大的 $x$ 值。注意，操作后线段占用的区间变为 $[\frac{1}{2}(\ell + x), r]$。
2. 操作 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$。

输出格式

对于每个测试用例，输出一行，表示将给定线段折叠以使最终线段长度尽可能短的方法数，模 998244353。

数据范围

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

说明

*需要注意的是，如果不存在整数 $a, b > 1$ 使得 $p = ab$，则大于 1 的整数 $p$ 是一个素数。

样例

输入样例 1

3
1 30
16 18
142857 240135

输出样例 1

3
1
63