Đếm nguyên tố

Cho \(T\) truy vấn. Mỗi truy vấn gồm hai số nguyên \(L\) và \(R\), yêu cầu đếm xem có bao nhiêu số nguyên tố nằm trong đoạn \([L, R]\).

Lưu ý: Số nguyên tố là số tự nhiên lớn hơn \(1\) và chỉ chia hết cho \(1\) và chính nó.

Input

• Dòng đầu chứa số nguyên \(T\) (\(1 \le T \le 10^5\)).

• \(T\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(L, R\) (\(1 \le L \le R \le 10^6\)).

Output

Với mỗi truy vấn, in ra một dòng chứa số lượng số nguyên tố trong đoạn \([L, R]\).

Example

Input:

3
1 10
5 10
11 11

Output:

4
2
1