Cho hai số nguyên dương ~L ≤ R~. Hãy đếm xem trong đoạn ~[L, R]~ có bao nhiêu số nguyên tố.

Input

• Dòng đầu ghi số nguyên dương ~T~ là số bộ test;
• ~T~ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương ~L ≤ R~ cách nhau bởi một dấu cách.

Giới hạn:

• ~1 ≤ T ≤ 10^2, 1 ≤ L ≤ R ≤ 10^6~.

Output

• Với mỗi cặp số ~L~ và ~R~, ghi ra trên một dòng số số nguyên tố trong đoạn ~[L, R]~.

Sample

Input #1

2
2 3
10 15

Output #1

2
2

Problem source: Chuyên Sơn La Online Judge