Số đặc biệt

Một số nguyên dương được gọi là số "đặc biệt" nếu số đó có đúng 3 ước nguyên dương đồng thời khác nhau.

**Yêu cầu:** Cho $M$ cặp số nguyên dương $(a; b)$, hãy đếm số lượng số "đặc biệt" $x$ thoả mãn $a \leq x \leq b$.

Yêu cầu: Cho \(M\) cặp số nguyên dương \((a; b)\), hãy đếm số lượng số "đặc biệt" \(x\) thoả mãn \(a \leq x \leq b\).

Input

Từ file SNUM.INP gồm:

• Dòng đầu là số nguyên dương \(M\) (\(1 \leq M \leq 10^5\));
• \(M\) dòng tiếp theo mỗi dòng chứa hai số nguyên dương \(a, b\) cách nhau bởi một khoảng trắng (\(1 \leq a \leq b \leq 10^6\)).

Output

Ghi ra file SNUM.OUT gồm \(M\) dòng, mỗi dòng là kết quả tương ứng tìm được.

Example

2
1 10
1 100

2
4

Scoring

• Có \(20\%\) số điểm ứng với (\(1 \leq M \leq 10^2; 1 \leq b \leq 10^2\));
• Có \(30\%\) số điểm ứng với (\(1 \leq M \leq 10^3; 1 \leq b \leq 10^3\));
• \(50\%\) số điểm còn lại không có giới hạn gì thêm.