Đèn đường thông minh

Thành phố Ánh Sáng đang triển khai một hệ thống đèn đường thông minh. Mỗi cột đèn được gán một mã số nguyên dương duy nhất, đánh số thứ tự từ \(1\) và tăng dần theo trục đường chính của thành phố. Theo thiết kế kỹ thuật:

• Chỉ những cột đèn có mã số là số nguyên tố mới được lắp đặt bộ điều khiển thông minh;

• Các cột còn lại là đèn thường.

Yêu cầu: Do quy mô thành phố rất lớn, mã số của cột đèn có thể lên tới hàng tỷ. Hệ thống quản lý yêu cầu bạn xử lý nhiều truy vấn, mỗi truy vấn cho biết: có bao nhiêu cột đèn thông minh từ cột đèn thứ \(L\) đến cột đèn thứ \(R\)?

Input

Dữ liệu vào có cấu trúc:

• Dòng đầu tiên chứa số nguyên \(T\) (\(1 \le T \le 10^5\)) là số lượng truy vấn;

• \(T\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(L, R\) (\(1 \le L \le R \le 2 \times 10^9\), \(R - L \le 10^6\)), được ghi cách nhau bởi dấu cách.

Ràng buộc:

• Subtask 1: \(30\%\) số test (\(30\%\) số điểm) có \(T \le 10^2\); \(L, R \le 10^3\);

• Subtask 2: \(40\%\) số test (\(40\%\) số điểm) có \(T \le 10^3\); \(L, R \le 10^6\);

• Subtask 3: \(30\%\) số test (\(30\%\) số điểm) có \(T \le 10^5\); \(L, R \le 2 \times 10^9\).

Output

In ra có cấu trúc:

• \(T\) dòng: tương ứng với mỗi truy vấn in ra một dòng, chứa số lượng cột đèn đường thông minh trong đoạn \([L, R]\).

Example

Input:

3
1 10
10 20
100 120

Output:

4
4
5

Note

Các số nguyên tố trong \([1, 10]\) là \(2, 3, 5, 7\); trong \([10, 20]\) là \(11, 13, 17, 19\); trong \([100, 120]\) là \(101, 103, 107, 109, 113\).