Một ngày, khi học sinh lớp \(1\) đang học về số học, giáo sư Wu Zi Mu đã ra bài tập như sau:

“Định nghĩa \(F(N)\) là số ước nguyên dương của \(N\). Ví dụ: \(F(12)=6,F(5)=2\).

Cho \(Q\) truy vấn, mỗi truy vấn chứa hai số \(A,B\). Nhiệm vụ là đếm tất cả số \(X\) nằm trong khoảng [A,B] mà \(F(X)\) là số nguyên tố lớn hơn \(2\).”

Học sinh lớp \(1\) đang cố tìm cách để giải bài này, nhưng không tìm ra được. Các bạn hãy giúp cho các học sinh đó nhé.

Input

• Gồm \(Q+1\) dòng:
• Dòng đầu tiên gồm số \(Q\) là số truy vấn.
• \(Q\) dòng tiếp theo, mỗi dòng chứa 2 số nguyên \(A,B\).

Output

• Gồm \(Q\) dòng là kết quả của \(Q\) truy vấn .

Constraints

• \(1 \leq A,B \leq 10^{12}\)
• \(1 \leq Q \leq 10^{5}\)

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(1 \leq A,B \leq 10^{3}, Q \leq 10^3\).
• Subtask \(2\) (\(30\%\) số điểm): \(1 \leq A,B \leq 10^{6}, Q \leq 10^5\).
• Subtask \(3\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

2
3 25
1 100 

4
7