Cho hai số nguyên \(a,b\). Tính tổng các số nguyên tố trong đoạn \([a,b]\).

Input

• Dòng 1 chứa số nguyên \(T(T≤10^5\) ),là số bộ test.

• \(T\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a,b (1≤a≤b≤10^5) \)thể hiện yêu cầu của một bộ test.

Output

• Ghi \(T\) dòng, mỗi dòng ghi một số nguyên là kết quả của test tương ứng.

Sample Input

2
1 20
10 20

Sample Output

77
60