题目描述

著名的硬件制造公司 $Processors\ for\ Professors$ 即将发布一款高度专业化的 $CPU$，其在数论等领域具有卓越的功能。例如，它有一个指令 $PFCAT$，该指令接受一个参数并返回该参数的所有质因数，且执行速度非常快。然而，它存在一个严重的问题。测试实验室的科学家们刚刚发现，$PFACT$ 指令对于一些特殊的输入值会失控，导致整个处理器爆炸。尽管这种效果可能很有趣，但这并不是它的预期工作方式。熟练的数学家们通过反复试验发现，这些爆炸性的数字都具有相同的、有趣的数论特性，这可能对故障排除有所帮助。

一个爆炸性数字是一个数字 $x = p_0 \cdot p_1 \cdot p_2 \cdot \ldots \cdot p_n$，其中所有的 $p_i$ 都是不同的质数，且满足 $p_i = A \cdot p_{i-1} + B$（$i = 1, 2, \ldots, n$）。其中 $n \geq 3$，$p_0 = 1$。$A$ 和 $B$ 总是整数，并且对于不同的爆炸性数字可能不同。

例如，处理器在分解数字 $4505$ 时会爆炸，因为 $4505 = 1 \cdot 5 \cdot 17 \cdot 53$，且 $5 = 3 \cdot 1 + 2$，$17 = 3 \cdot 5 + 2$，$53 = 3 \cdot 17 + 2$，而数字 $5$、$17$ 和 $53$ 都是质数。在这种情况下，$A = 3$ 和 $B = 2$。

你的任务是编写一个计算机程序，帮助该公司通过计算给定整数范围内存在的爆炸性数字的数量来评估错误的影响。

输入格式

输入的第一行包含一个整数 $0 \leq N \leq 100$，表示测试用例的数量。接下来的每个测试用例占一行，包含两个整数 $x_L$ 和 $x_H$，用一个空格分隔。这些数字满足 $0 \leq x_L \leq x_H \leq 2,000,000,000$。

输出格式

对于每个测试用例，输出在范围 $x_L \leq x \leq x_H$ 内存在的爆炸性数字的数量。

示例输入 1

2
4505 4505
0 5000

示例输出 1

1
5

来源

$Svenskt\ Mästerskap\ i\ Programmering/Norgesmesterskapet\ 2003$