A11758. Sad powers
编程题
普及/提高-
知识点
题目描述
You're given $Q$ queries of the form $(L,R)$ .
For each query you have to find the number of such $x$ that $L<=x<=R$ and there exist integer numbers $a>0$ , $p>1$ such that $x=a^{p}$ .
For each query you have to find the number of such $x$ that $L<=x<=R$ and there exist integer numbers $a>0$ , $p>1$ such that $x=a^{p}$ .
输入格式
The first line contains the number of queries $Q$ $(1<=Q<=10^{5})$ .
The next $Q$ lines contains two integers $L$ , $R$ each $(1<=L<=R<=10^{18})$ .
The next $Q$ lines contains two integers $L$ , $R$ each $(1<=L<=R<=10^{18})$ .
输出格式
Output $Q$ lines — the answers to the queries.
输入输出样例
输入 #1
6 1 4 9 9 5 7 12 29 137 591 1 1000000
输出 #1
2 1 0 3 17 1111
说明/提示
In query one the suitable numbers are $1$ and $4$ .