U729429 小魏的素数

小魏非常喜欢素数，他经常在各种数字中寻找素数的踪迹。最近他学习了同余方程，于是决定将两者结合起来，并以此来考察大家对时间复杂度的优化能力。

**本题有多组测试数据。** 给定闭区间 $[L, R]$，请你找出在该区间内，满足以下所有条件的整数 $x$ 的个数： 1. $x \bmod 71 = 11$ 2. $x \bmod 73 = 13$ 3. $x$ 是一个素数

第一行包含一个正整数 $T$，表示测试数据的组数。 接下来 $T$ 行，每行包含两个正整数 $L$ 和 $R$，两个数字之间由一个空格隔开，表示一组测试数据。

对于每组测试数据，输出一行一个整数，表示满足所有条件的 $x$ 的数量。

**【名词解释：素数】** **素数**，又称质数，是指在大于 $1$ 的自然数中，除了 $1$ 和它本身以外，不再有其他因数的自然数。 **【数据规模与约定】** * 对于 $30\%$ 的测试数据，保证 $1 \le L \le R \le 10^5$，且 $T \le 10$。 * 对于 $100\%$ 的测试数据，保证 $1 \le T \le 100$，$1 \le L \le R \le 10^9$ * 所有测试数据满足 $\sum_{i=1}^{T}(R_i-L_i+1)\le 10^{11}$。