Trong một trường THPT, Câu lạc bộ Toán học tổ chức hoạt động chọn mã thành viên đặc biệt. Mỗi mã thành viên là một số nguyên dương ~x~.

Với mỗi số nguyên dương ~n~, gọi ~d(n)~ là số lượng ước dương của ~n~.

Một mã số ~x~ được gọi là đạt chuẩn nếu ~d(x)~ là một số nguyên tố lẻ.

Ban tổ chức đưa ra ~Q~ danh sách, mỗi danh sách tương ứng với một đoạn số ~[L, R]~. Với mỗi đoạn như vậy, hãy xác định trong các số từ ~L~ đến ~R~ có bao nhiêu mã số đạt chuẩn.

Input

• Dòng đầu chứa số nguyên ~Q~ là số lượng truy vấn ~(1 \le Q \le 2 \cdot 10^5)~.

• ~Q~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~L~ và ~R~ ~(1 \le L \le R \le 10^{14})~.

• Mỗi truy vấn yêu cầu đếm số lượng ~x~ thuộc đoạn ~[L, R]~ sao cho ~d(x)~ là một số nguyên tố lẻ.

Output

Với mỗi truy vấn, in ra trên một dòng một số nguyên là đáp án tương ứng.

Scoring

Sample Input 1

3
1 10
11 100
1 1000

Sample Output 1

2
5
16

Notes

Truy vấn ~[1, 10]~: các số hợp lệ là ~4 = 2^2~ và ~9 = 3^2~. Cả hai đều có đúng ~3~ ước dương.

Truy vấn ~[11, 100]~: các số hợp lệ là ~16, 25, 49, 64, 81~.

Truy vấn ~[1, 1000]~: có ~16~ số hợp lệ, gồm các bình phương của số nguyên tố không vượt quá ~1000~ và thêm hai số ~625 = 5^4~, ~729 = 3^6~.