Một số nguyên dương được gọi là số nguyên tố nếu nó có chính xác hai ước số nguyên dương.

Yêu cầu: Cho hai số tự nhiên \(l\) và \(r (l≤r)\), đếm số lượng các số nguyên tố từ \(l\) tới \(r\).

Input

• Dòng thứ nhất chứa số nguyên \(T(1≤T≤10^5)\),là số bộ test.

• \(T\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(l\) và \(r (1≤l≤r≤2*10^8)\).

Output

• Gồm \(T\) dòng, Dòng thứ \(i\) ghi số lượng số lượng số nguyên tố có giá trị từ \(l\) tới \(r\) ứng với test thứ \(i\).

Ràng buộc

• Subtask 1: \(T≤10^3;l≤r≤10^7\)

• Subtask 2: Không có ràng buộc gì thêm.

Sample Input

2
1 7
3 19

Sample Output

4
16