Almost prime numbers are the non-prime numbers which are divisible by only a single prime number.

In this problem your job is to write a program which finds out the number of almost prime numbers

within a certain range.

Input

First line of the input file contains an integer N (N ≤ 600) which indicates how many sets of inputs

are there. Each of the next N lines make a single set of input. Each set contains two integer numbers

low and high (0 < low ≤ high < 1012).

Output

For each line of input except the first line you should produce one line of output. This line contains

a single integer, which indicates how many almost prime numbers are within the range (inclusive)

low . . . high.

Sample Input

3

1 10

1 20

1 5

Sample Output

3

4

1

 

题意：给你 一个范围 a,b，找出这个范围中 满足 x = p^k (p为素数，k > 1)  的数的个数

题解： ab,范围是10的12次方 我们找出1e6内的素数 ，打表出所有可能形成 的数去重排序 ，每次二分找下标就好了

       ans(b) - ans(a-1)就是答案

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include
           
            using namespace std ;typedef long long ll;const int N=1000000;ll a, b, prime[N + 2], now[N+2];int H[N + 2], cnt, scc;void prime_table() { cnt = 0; H[1] = 1; for(int i = 2; i <= N ; i++) { if(!H[i]) { for(int j = i + i ; j <= N ; j += i) H[j] = 1; prime[++cnt] = i; } } scc = 0; for(int i = 1 ; i <= cnt ; i++) { for(ll j = prime[i] * prime[i] ; j <= 1e12 ; j *= prime[i]) { now[scc++] = j; } } sort(now, now + scc); scc = unique(now,now + scc) - now ;}ll solve(ll x) { ll ans = upper_bound(now,now + scc,x) - now; return ans;}int main() { prime_table(); int T; scanf("%d",&T); while(T--) { scanf("%lld%lld",&a,&b); ll ans = solve(b) - solve(a-1); printf("%lld\n", ans); } return 0;}