Số nguyên dương \(X\) được gọi là "Nguyên tố cặp" nếu:

1. \(X\) là một số nguyên tố.
2. Tồn tại ít nhất một vị trí chia \(X\) thành 2 phần khác rỗng, mỗi phần đều tạo thành một số nguyên tố.

Ví dụ:

• \(317\) là nguyên tố cặp vì có thể chia thành \(3\) và \(17\), hoặc \(31\) và \(7\).
• \(307\) là nguyên tố cặp vì có thể chia thành \(3\) và \(07 \to\) tương đương \(3\) và \(7\).
• \(29\) không phải nguyên tố cặp vì chia thành \(2\) và \(9\) (\(9\) không phải số nguyên tố).
• \(103\) không phải nguyên tố cặp vì chia thành \((1, 03)\) và \((10, 3)\) đều không phải cặp nguyên tố.

Yêu cầu: Cho hai số nguyên dương \(L, R\). Hãy đếm số lượng số nguyên tố cặp trong đoạn \([L, R]\).

Input

• Dòng đầu chứa số nguyên \(T\) (\(1 \le T \le 10^5\)) là số lượng test.
• Mỗi dòng trong \(T\) dòng tiếp theo chứa 2 số \(L, R\) (\(1 \le L \le R \le 10^7\)).

Output

• Gồm \(T\) dòng, mỗi dòng ghi kết quả của bộ test tương ứng được cho trong dữ liệu vào.

Example

3
10 60
310 320
1 10

3
3
0

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(T \le 100; 1 \le L \le R \le 1000\).
• Subtask \(2\) (\(25\%\) số điểm): \(T \le 100; 1 \le L \le R \le 10^6\).
• Subtask \(3\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.