Lũy thừa hoàn hảo

Một số nguyên dương $x$ được gọi là lũy thừa hoàn hảo nếu tồn tại các số nguyên $a>0$ và $p>1$ sao cho $x=a^p$. Ví dụ: $1=1^2$, $4=2^2$, $8=2^3$, $9=3^2$ đều là lũy thừa hoàn hảo, còn $2,3,5,6,7$ thì không.

Cho $Q$ truy vấn, mỗi truy vấn gồm hai số nguyên $L,R$. Với mỗi truy vấn, hãy đếm số lượng lũy thừa hoàn hảo $x$ thỏa mãn $L\le x\le R$.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $Q$ — số truy vấn.
• $Q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $L,R$.

Dữ liệu ra

In ra $Q$ dòng, dòng thứ $i$ là đáp án của truy vấn thứ $i$.

Ràng buộc

• $1\le Q\le {10}^5$
• $1\le L\le R\le {10}^{18}$

Ví dụ