Một số nguyên dương gọi là "Số đặc biệt" nếu số lượng các ước số của nó là một số nguyên tố.

Ví dụ:

• Số \(4\) có các ước là \(\{1, 2, 4\}\). Số lượng ước là \(3\). Vì \(3\) là số nguyên tố nên \(4\) là số đặc biệt.
• Số \(6\) có các ước là \(\{1, 2, 3, 6\}\). Số lượng ước là \(4\). Vì \(4\) không phải là số nguyên tố nên \(6\) không phải là số đặc biệt.

Nam được cô giáo giao cho một danh sách các câu hỏi, mỗi câu hỏi yêu cầu đếm xem trong đoạn từ \([L, R]\) có bao nhiêu số đặc biệt. Vì danh sách rất dài nên Nam phải viết một chương trình để giải quyết nhanh chóng.

Yêu cầu: Cho \(Q\) câu hỏi, mỗi câu hỏi gồm hai số nguyên \(L\) và \(R\). Hãy đếm số lượng số đặc biệt trong đoạn \([L, R]\).

Input

• Dòng đầu tiên chứa số nguyên \(Q\) (\(1 \le Q \le 10^5\)) là số lượng câu hỏi.
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(L\) và \(R\) (\(1 \le L \le R \le 10^6\)).

Output

• Ghi ra \(Q\) dòng, mỗi dòng là đáp án cho câu hỏi tương ứng.

Example

2
1 5
7 10

4
2

Scoring

• \(30\%\) số điểm tương ứng \(Q \le 100\) và \(R \le 1000\).
• \(40\%\) số điểm tương ứng \(Q \le 10^5\) và \(R \le 10^5\).
• \(30\%\) số điểm tương ứng \(Q \le 10^5\) và \(R \le 10^6\).