Hãy đếm trong đoạn [a, b] các số nguyên dương thỏa mãn yêu cầu: số lượng các ước của nó là một số nguyên tố.

Dữ liệu vào

• Dòng 1: chứa số T là số lượng các đoạn cần đếm
• Dòng 2: T dòng tiếp theo, mỗi dòng chứa một cặp số nguyên a và b

Kết quả

• Gồm T dòng, mỗi dòng là kết quả tương ứng

Ví dụ 1:

INPUT

2
2 5
1 100

OUTPUT

4
32

Ràng buộc

• Subtask1: có 30% số điểm 1 ≤ a ≤ b ≤ 200 và T ≤ 100
• Subtask2: có 30% số điểm 1 ≤ a ≤ b ≤ 2000 và T ≤ 1000
• Subtask3: có 40% còn lại ~1 ≤ a ≤ b ≤ 10^6~ và ~T ≤ 10^5~