Mô tả và yêu cầu

Hoán vị dãy các chữ số hệ 10 có một tính chất thú vị: hiệu của 2 hoán vị luôn là
một số chia hết cho 9. Thật là bất ngờ phải không? Ví dụ: |458967 – 456879| =
2088 = 9 ∗ 232; |28 – 82| = 54 = 9.6

Ta lưu ý đến một khía cạnh khác của giá trị tuyệt đối hiệu này. Có những số mà
hiệu giữa nó và một hoán vị của nó có dạng 9𝑝, trong đó 𝑝 là số nguyên tố nhỏ hơn
1111111. Những số này gọi là hoán vị nguyên tố. Ví dụ, 92 – 29 = 63 = 9 ∗ 7. Số
7 là số nguyên tố, vì vậy 92 được gọi là hoán vị nguyên tố.

Yêu cầu: Cho 2 số nguyên dương 𝐴 và 𝐵 (0 < 𝐴, 𝐵 ≤ 99 999 999, |𝐴 −
𝐵| ≤ 1000). Hãy xác định khoảng [𝐴, 𝐵] chứa bao nhiêu hoán vị nguyên tố.

Dữ liệu: Vào từ thiết bị nhập chuẩn:

 Dòng đầu tiên chứa số nguyên 𝑇 là số lượng Tests,

 𝑇 dòng sau: mỗi dòng chứa 2 số nguyên 𝐴 và 𝐵 cách nhau bởi một dấu
cách

Kết quả: Đưa ra thiết bị xuất chuẩn: ứng với mỗi cặp 𝐴, 𝐵 đưa ra số lượng hoán
vị nguyên tố tìm được, mỗi kết quả trên một dòng.

Ví dụ

INPUT              OUTPUT

                                 2                  0
                                 1 10               5
                                 1 20