Một số nguyên dương được gọi là số 3D nếu thỏa mãn đồng thời 3 điều kiện:

1. Là số nguyên tố.
2. Tổng các chữ số của nó cũng là số nguyên tố.
3. Tích các chữ số của nó cũng là số nguyên tố.

Cho T đoạn, mỗi đoạn là một cặp số nguyên dương A, B (1 ≤ A ≤ B ≤ 10^7).
Với mỗi đoạn, hãy đếm số lượng số 3D trong đoạn đó (bao gồm cả A và B nếu thỏa mãn).

Input (file SO3D.INP)

• Dòng 1: số nguyên dương T (T ≤ 1000) – số lượng đoạn.
• T dòng tiếp theo: mỗi dòng chứa hai số nguyên A và B, cách nhau bởi dấu cách.

Output (file SO3D.OUT)

• Gồm T dòng.
• Dòng thứ i ghi số lượng số 3D trong đoạn thứ i tương ứng của đầu vào.

Giới hạn

• Có 20% số test (ứng với 20% số điểm) có 10 ≤ B – A + 1 ≤ 10^4.
• Có 50% số test (ứng với 50% số điểm) có 10^4 < B – A + 1 ≤ 10^6.
• Có 30% số test (ứng với 30% số điểm) có 10^6 < B – A + 1 ≤ 10^7.

Example

SO3D.INP

3
1 10
17 22
100 200

SO3D.OUT

4
0
3

Giải thích:

• Từ 1 đến 10 có 4 số 3D: 2, 3, 5, 7.
• Từ 17 đến 22 không có số 3D nào.
• Từ 100 đến 200 có 3 số 3D: 113, 131, 151.