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.

Input

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

Output

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

Example

2
1 50
10000000 10000050

15
1