Số nguyên tố

Số tự nhiên \(p\) là số nguyên tố nếu \(p > 1\) và chỉ có 2 ước là \(1\) và \(p\).

Yêu cầu: Cho 2 số tự nhiên \(a\) và \(b\). Tính tổng các số nguyên tố và đếm số lượng số nguyên tố thuộc đoạn \([a, b]\).

Input

• Dòng đầu tiên ghi số nguyên dương \(T\) (\(T \le 10^6\));
• \(T\) dòng tiếp theo, mỗi dòng ghi 2 số tự nhiên \(a\) và \(b\) (\(0 < a \le b \le 10^6\)).

Output

Gồm \(T\) dòng, mỗi dòng ghi 2 số là tổng các số nguyên tố và số lượng số nguyên tố thuộc đoạn \([a, b]\) tương ứng.

Example

2
15 20
1 5

36 2
10 3

Scoring

• Có \(50\%\) số test ứng với \(50\%\) số điểm thỏa mãn: \(T = 1; \ a, b \le 10^3\).
• Có \(30\%\) số test ứng với \(30\%\) số điểm thỏa mãn: \(T \le 10; \ a, b \le 10^5\).
• \(20\%\) số test còn lại ứng với \(20\%\) số điểm của bài không có ràng buộc gì thêm.