폭발하는 CPU

한 반도체 회사가 정수론 분야에 특화된 고성능 CPU를 준비하고 있다. 이 CPU에는 매개변수 하나를 받아 그 수의 모든 소인수를 매우 빠르게 반환하는 PFACT 명령어가 있다.

그런데 심각한 결함이 하나 있다. 어떤 특별한 입력값에 대해 PFACT 명령어가 오작동하여 프로세서 전체가 "폭발"해 버린다. 조사 결과, 프로세서를 폭발시키는 수들은 모두 같은 정수론적 구조를 공유한다는 사실이 밝혀졌다.

폭발하는 수(explosive number) 란 다음 조건을 모두 만족하는 수 $x = p_0 \cdot p_1 \cdot p_2 \cdots p_n$ 이다.

• 모든 $p_i$ 는 서로 다른 소수이다.
• $p_0 = 1$ 이다.
• 어떤 정수 $A$, $B$ 에 대해, $i = 1, 2, \ldots, n$ 인 모든 $i$ 에서 $p_i = A \cdot p_{i-1} + B$ 가 성립한다.
• $n \geq 3$ 이다. 즉 소인수 $p_1, \ldots, p_n$ 이 3개 이상이다.

정수 $A$ 와 $B$ 는 폭발하는 수마다 다를 수 있다.

예를 들어 $4505 = 1 \cdot 5 \cdot 17 \cdot 53$ 은 폭발하는 수이다. $A = 3$, $B = 2$ 로 두면 $5 = 3 \cdot 1 + 2$, $17 = 3 \cdot 5 + 2$, $53 = 3 \cdot 17 + 2$ 이고 $5$, $17$, $53$ 이 모두 소수이기 때문이다.

주어진 정수 구간 안에 폭발하는 수가 몇 개 존재하는지 세는 프로그램을 작성하라.

첫 번째 줄에 테스트 케이스의 개수 $N$ 이 주어진다 ($0 \leq N \leq 100$).

이어지는 각 테스트 케이스는 한 줄에 두 정수 $x_L$ 과 $x_H$ 가 공백 하나로 구분되어 주어진다 ($0 \leq x_L \leq x_H \leq 2 \times 10^9$).

각 테스트 케이스마다 $x_L \leq x \leq x_H$ 범위 안에 존재하는 폭발하는 수의 개수를 한 줄에 하나씩 출력한다.