1214 - Cubic-free numbers II

Time Limit : 10 Second

Memory Limit : 128 MB

Submission: 803

Solved: 92

Description
A positive integer n is called cubic-free, if it can't be written in this form n = x*x*x*k, while x is a positive integer larger than 1. Now give you two Integers L and R, you should tell me how many cubic-free numbers are there in the range [L, R). Range [L, R) means all the integers x that L <= x < R.
Input
The first line is an integer T (T <= 100) means the number of the test cases. The following T lines are the test cases, for each line there are two integers L and R (L <= R <= ).
Output
For each test case, output one single integer on one line, the number of the cubic-free numbers in the range [L, R).
sample input
3
1 10
3 16
20 100
sample output
8
12
67
hint
source
© 2015 HUST ACMICPC TEAM. All Right Reserved.