Một số \(x\) được gọi là đẹp nếu số lượng các số nguyên tố trong đoạn từ \(1\) đến \(x\) là số nguyên tố.

Cho số nguyên dương \(L,R\). Đếm số lượng các số đẹp trong \([L,R]\).

Input

• Dòng thứ nhất chứa số \(T (1 ≤ T ≤ 10^5)\) – là số bộ test;

• T dòng tiếp theo, mỗi dòng gồm hai số nguyên \(L,R (L ≤ R ≤ 10^6\) )

Output

• In ra \(T\) dòng, dòng thứ \(i\) là kết quả của bộ test thứ \(i\).

Sample Input

2
3 10
4 12

Sample Output

4
5