1214  Cubicfree numbers II
Time Limit : 10 Second
Memory Limit : 128 MB
Submission: 803
Solved: 92
 Description
 A positive integer n is called cubicfree, 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 cubicfree 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 cubicfree numbers in the range [L, R).
 sample input

3 1 10 3 16 20 100
 sample output

8 12 67
 hint
 source