Cho hai số \(L, R\).

Nhiệm vụ của bạn là hãy đếm tất cả các số có đúng ba ước số trong khoảng \([L, R]\).

Ví dụ \(L =1, R =10\), ta có kết quả là \(2\) vì chỉ có số \(3\) và \(9\) là có đúng \(3\) ước số.

Input

• Dòng đầu tiên đưa vào số lượng test \(T\ (1 \le T \le 100)\).
• Những dòng kế tiếp đưa vào các bộ test. Mỗi bộ test là cặp số \(L, R\ (1 \le L, R \le 10^{12})\).

Output

• Đưa ra kết quả mỗi test theo từng dòng.

Example

2
1 10
1 1000000000000

2
78498