An rất yêu thích môn Toán học, đặc biệt là kiến thức về số học. Khi làm bài tập về bội số, An gọi một số nguyên dương là "số may mắn" nếu nó là bội của đúng bốn số nguyên dương khác nhau. Ví dụ ~2026~ là "số may mắn" vì là bội của ~1, 2, 1013, 2026~. Với đam mê của mình, An rất muốn tìm tất cả các "số may mắn" trong đoạn bất kỳ.

Yêu cầu: Cho ~Q~ đoạn ~[A, B]~, đếm số lượng các "số may mắn" trong từng đoạn.

Input

• Dòng đầu tiên có một số nguyên dương ~Q~ (~Q \le 10^5~);

• ~Q~ dòng tiếp theo, mỗi dòng có ~2~ số nguyên dương ~A, B~ (~A \le B \le 10^8~);

Dữ liệu đảm bảo ~\max\{B_1, B_2, \dots, B_Q\} - \min\{A_1, A_2, \dots, A_Q\} \le 10^6~.

Output

~Q~ dòng, mỗi dòng là số lượng "số may mắn" trong đoạn ~[A, B]~ tương ứng.

Scoring

Sample Input 1

2
1 10
100 1000

Sample Output 1

3
260

Notes

Đoạn ~[1, 10]~ có ~3~ "số may mắn" là: ~6, 8, 10~.

Đoạn ~[100, 1000]~ có ~260~ "số may mắn".