Exploding CPU

A hardware company is preparing a high-performance CPU specialized for number theory. Among its instructions is PFACT, which takes a single argument and returns all of that number's prime factors at remarkable speed.

There is, however, a serious flaw: for certain special inputs the PFACT instruction malfunctions and makes the whole processor "explode". Investigation revealed that every number that triggers an explosion shares the same number-theoretic structure.

An explosive number is a number $x = p_0 \cdot p_1 \cdot p_2 \cdots p_n$ such that:

• all $p_i$ are distinct prime numbers;
• $p_0 = 1$;
• $p_i = A \cdot p_{i-1} + B$ for every $i = 1, 2, \ldots, n$, where $A$ and $B$ are integers;
• $n \geq 3$ (that is, there are at least three prime factors $p_1, \ldots, p_n$).

The integers $A$ and $B$ may differ from one explosive number to another.

For example, $4505 = 1 \cdot 5 \cdot 17 \cdot 53$ is explosive: taking $A = 3$ and $B = 2$ gives $5 = 3 \cdot 1 + 2$, $17 = 3 \cdot 5 + 2$, and $53 = 3 \cdot 17 + 2$, and $5$, $17$, $53$ are all prime.

Write a program that counts how many explosive numbers lie within a given range of integers.

The first line contains the number of test cases $N$ ($0 \leq N \leq 100$).

Each of the following test cases is given on one line as two integers $x_L$ and $x_H$ separated by a single space ($0 \leq x_L \leq x_H \leq 2 \times 10^9$).

For each test case, print on its own line the number of explosive numbers $x$ with $x_L \leq x \leq x_H$.