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 \le T \le 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 \le L_i \le R_i \le 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\)).

Dữ liệu ra

• 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\)).

Scoring

• 50% số điểm của bài tương ứng với các test có \((L_i, R_i \le 10^5\)) và tổng độ dài các đoạn truy vấn không vượt quá \((10^5\))

Input 1

2
1 50
10000000 10000050

Output 1

15
1