Một số nguyên dương ~x~ được gọi là số ma thuật nếu số lượng ước số của nó là một số nguyên tố lớn hơn 2. Ví dụ: các số ~9, 81, 15625~ là các số ma thuật (~9~ có ~3~ ước là ~1, 3~ và ~9~; ~81~ có ~5~ ước là ~1, 3, 9, 27~ và ~81~; ~15625~ có ~7~ ước); số ~6, 8~ không là số ma thuật. Đề thi vào trường đào tạo Pháp sư năm nay như sau: "Cho hai số nguyên dương ~a, b~ (~a \le b~). Hãy tìm số lượng các số ma thuật trong đoạn ~[a; b]~".

Yêu cầu: Hãy lập trình tìm số lượng các số ma thuật trong đoạn ~[a; b]~.

Dữ liệu

Từ file văn bản CAU5.INP:

• Dòng 1 chứa số nguyên dương ~T~ là số lượng bộ test;
• ~T~ dòng tiếp theo, dòng thứ ~i~ (~i = \overline{1, T}~) gồm hai số nguyên dương ~a, b~ (~a \le b~).

Kết quả

Đưa ra file văn bản CAU5.OUT:

• ~T~ dòng, dòng thứ ~i~ là kết quả của bộ test thứ ~i~.

Ví dụ

CAU5.INP

5
12 400
412 1000
32 100
1910 3000
1 100

CAU5.OUT

9
5
3
3
7

Giới hạn

• Có 10% số test ứng với 10% số điểm của bài thỏa mãn điều kiện: ~1 \le a, b \le 200, T \le 100~;
• Có 10% số test ứng với 10% số điểm của bài thỏa mãn điều kiện: ~1 \le a, b \le 2000, T \le 1000~;
• Có 10% số test ứng với 10% số điểm của bài thỏa mãn điều kiện: ~1 \le a, b \le 10^6, T \le 1000~;
• Có 10% số test ứng với 10% số điểm của bài thỏa mãn điều kiện: ~1 \le a, b \le 10^6, T \le 10^5~;
• Có 60% số test còn lại ứng với 60% số điểm của bài thỏa mãn điều kiện: ~10^6 < a, b \le 10^{12}~.