Một số nguyên dương được gọi là số đặc biệt nếu nó có đúng ~3~ ước nguyên dương đôi một 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~.

INPUT

• 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 kết quả gồm ~M~ dòng, mỗi dòng là kết quả tương ứng tìm được.

SAMPLE INPUT

2
1 10
1 100

SAMPLE OUTPUT 1

2
4

SUBTASKS

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