Số nguyên dương \(x\) được gọi là số đặc biệt nếu \(x\) có đúng \(4\) ước dương.

Ví dụ 8 là số đặc biệt vì 8 có đúng 4 ước dương đó là 1, 2, 4, 8. Số 16 không là số đặc biệt vì 16 chỉ có 5 ước dương đó là 1, 2, 4, 8, 16.

Yêu cầu: Tính số lượng các số đặc biệt trong đoạn \(a,b.\)

Dữ liệu vào từ tệp văn bản UP16.INP có cấu trúc:

• Dòng 1: chứa số \(T(T<=10^6)\) là số lượng các đoạn cần đếm.

• Dòng 2: \(T\) dòng tiếp theo, mỗi dòng chứa một cặp số nguyên \(a\) và \(b (a≤b≤10^6 ).\)

Kết quả ghi vào tệp văn bản UP16.OUT có cấu trúc:

• Gồm \(T\) dòng, mỗi dòng là kết quả tương ứng với input

Ràng buộc

• Subtask1: có 30% số điểm \(T≤10^2;b≤10^3.\)

• Subtask2: có 30% số điểm \(T≤10^3;b≤10^5\)

• Subtask3: có 40% số điểm với \(T≤10^6;b≤10^6. \)

Sample Input

3
6 9
10 15
20 33

Sample Output

2
3
5

Giải thích:

• Trong đoạn từ 6 đến 9 có hai số đặc biệt đó là số 6 và số 8.

• Trong đoạn từ 10 đến 15 có ba số đặc biệt đó là số 10, 14, 15.

• Trong đoạn từ 20 đến 33 có 5 số đặc biệt đó là số : 21, 22, 26, 27, 33.