#2615 안 제곱 수

4 s   128 MB  

Description

안 제곱 수란, 어떤 수 X가 1보다 큰 제곱수로 나누어 떨어지지 않는 수 이다. 어떤 구간이 주어졌을 때, 구간 사이에 안 제곱 수가 몇 개 있는지 출력 하라.

Input

test case $t$ $(1 \leq t \leq 100)$ 가 주어지고, 구간 $[a, b]$가 주어진다. $(1 \leq a \leq b \leq 10^{12})$

Output

구간 [a,b] 에서 안 제곱 수의 개수를 출력하라.

Sample Input

Sample Output

1
1 10
7

Source

2015 ANSI Summer Coding Camp / BOJ 1016 / data set by wowoto9772(최승주)