Một nhà toán học đang làm việc với các số nguyên tố cần sự giúp đỡ của bạn. Cụ thể, nhà toán học có ~t~ câu hỏi, mỗi câu hỏi là một cặp số ~l~ và ~r~, bạn cần trả lời số lượng số nguyên tố nằm trong đoạn ~[l,r]~, tính cả hai đầu. Nhận thấy các thí sinh tham gia Kỳ thi Olympic Truyền thống 30-4 có khả năng trả lời được câu hỏi này, nhà Toán học nhờ các bạn trợ giúp. Các bạn hãy giúp nhà Toán học nhé.

Yêu cầu: Hãy viết chương trình trả lời các truy vấn của nhà Toán học.

Dữ liệu vào:

• Dòng đầu chứa số nguyên dương ~t~ ~(1≤t≤1000)~ là số truy vấn.
• ~t~ dòng tiếp theo, mỗi dòng ghi hai số nguyên dương, dòng thứ ~i + 1~ ghi cặp số ~l_i,r_i~ ~(1 ≤ l_i≤ r_i≤ 10^9)~ là các tham số của truy vấn thứ ~i~.
• Tổng độ dài của các đoạn truy vấn không vượt quá ~10^6~.

Kết quả:

• Gồm ~t~ dòng, dòng thứ ~i~ chứa một số nguyên là câu trả lời của truy vấn thứ ~i~

Ràng buộc:

• 50% số điểm của bài tương ứng với các test có ~l_i,r_i ≤10^5~ và tổng độ dài các đoạn truy vấn không vượt quá ~10^5~.

Ví dụ:

Input

2
1 50
10000000 10000050 

Output

15
1