Số đặc biệt

Trong giờ học môn Toán, thầy giáo đưa ra quy ước "Số đặc biệt" là số nguyên dương có đúng 4 ước số dương. Ví dụ:

• 8 có 4 ước số dương gồm 1, 2, 4, 8 nên là số đặc biệt
• 25 có 3 ước số dương gồm 1, 5, 25 nên không phải số đặc biệt

Thầy giáo cho mỗi bạn hai số nguyên dương \(L, R\) (\(L < R \leq 10^6\)). Yêu cầu đếm số lượng số đặc biệt trong đoạn \([L; R]\).

Input

Tệp SODB.INP gồm:

• Dòng đầu: Số nguyên dương \(T\) (\(T \leq 10^6\)) - số lượng cặp số
• \(T\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(L, R\)

Output

Ghi ra tệp SODB.OUT gồm \(T\) dòng, mỗi dòng là số lượng số đặc biệt tương ứng.

Example

3
6 9
10 15
20 33

2
3
5

Scoring

• 60% tests: \(T \leq 100\), \(R \leq 1000\)
• 30% tests: \(100 < T \leq 1000\), \(R \leq 10^5\)
• 10% tests: \(1000 < T \leq 10^6\), \(R \leq 10^6\)