Trong giờ Tin học, Lam tìm hiểu dãy số ~P_1, P_2, P_3 \dots~ là dãy số nguyên tố được sắp xếp theo thứ tự tăng dần: ~2, 3, 5, 7, 11, \dots~. Lam gọi một số nguyên tố ~P_i~ ~(i \ge 2)~ trong dãy là số nguyên tố kỳ lạ nếu tồn tại một vị trí ~j~ ~(1 \le j \le i - 1)~ thỏa mãn: $$P_i = \frac{P_j + P_{i+1}}{2}$$ Như vậy, các số nguyên tố kỳ lạ là ~5, 7, \dots~ Vì: ~5 = \frac{3 + 7}{2}; 7 = \frac{3 + 11}{2} \dots~

Yêu cầu: Bạn hãy giúp Lam đếm số lượng số nguyên tố kỳ lạ trong đoạn ~[a, b]~.

Input

• Dòng đầu tiên chứa một số nguyên dương ~T~ là số lượng đoạn cần đếm.

• ~T~ dòng tiếp theo, mỗi dòng ghi hai số nguyên dương ~a, b~.

Output

Ghi ra thiết bị ra chuẩn gồm ~T~ dòng, mỗi dòng ghi một số nguyên là số lượng số nguyên tố kỳ lạ trong đoạn tương ứng.

Scoring

Sample Input 1

2
1 5
5 11

Sample Output 1

1
2