## NGIRL - Namit In Trouble

no tags

Namit's girlfriend's birthday is coming next week. He went to a gift shop and saw N gifts are arranged in a single row in such a way that the position at which the gift is placed is equal to its price. (Position starts from 1.)

Namit's girlfriend being a maths student like those numbers which have exactly 3 divisors, so Namit decide to buy only those gifts which are placed at a position which have only 3 divisors, but Namit's girlfriend likes gifts whose price are above a certain amountK.

Now Namit wants to know total choices he have and how many gifts his girlfriend like for a given value of N.

### Input

Input starts with 1<=T<=1000 (number of test cases). Then T lines follows each containing two integer 1<=N<10^10 (number of gifts at gift shop) and 1<=K<=10^10.

### Output

You program should output two values indicating total number of choices and the number of gifts Namit's girlfriend likes.

### Example

```Input:
3
10 2
20 7
10 4

Output:
2 2
2 1
2 1```

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````#include <bits/stdc++.h7gt;
using namespace std;
typedef long long ll;

#define MOD                 1000000007LL
#define EPS                 1e-9
#define io                  ios_base::sync_with_stdio(false);cin.tie(NULL);
#define M_PI                3.14159265358979323846

template <typename T> T gcd(T a, T b){return (b==0)?a:gcd(b,a%b);}
template <typename T> T lcm(T a, T b){return a*(b/gcd(a,b));}
template <typename T> T mod_exp(T b, T p, T m){T x = 1;while(p){if(p&1)x=(x*b)%m;b=(b*b)%m;p=p>>1;}return x;}
template <typename T> T invFermat(T a, T p){return mod_exp(a, p-2, p);}
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}

const int MAXN = 1e6+5;
vector<ll> primes;
ll isPrime[MAXN];
vector<ll> primes_squares;

void sieve(){
isPrime[0] = isPrime[1] = 1;
for(int i = 2;i <= 1000000; i++){
if(isPrime[i] == 0){
primes.push_back(i);
if(i*1LL*i <= 1000000){
for(int j = i*i;j <= 1000000; j+=i)
isPrime[j] = 1;
}
}
}
}

void pre(){
for(auto i : primes){
primes_squares.push_back(i*1LL*i);
}
}

int main(){
io;
sieve();
pre();
int t;
cin >> t;
while(t--){
ll n, k;
cin >> n >> k;
// ans1 is numbers which have 3 divisors less than equal to n
if(n <= 3)
cout << 0 << " " << 0 << endl;
else{
ll ans1 = upper_bound(primes_squares.begin(), primes_squares.end(), n) - primes_squares.begin() - 1;
ans1+=1;
ll ans2 = upper_bound(primes_squares.begin(), primes_squares.end(), k) - primes_squares.begin() - 1;
ans2+=1;
cout << ans1 << " ";
if(ans1 >= ans2)
cout << (ans1-ans2) << endl;
else
cout << 0 << endl;
}
}
return 0;
}``````
Copy The Code &

Input

cmd
3
10 2
20 7
10 4

Output

cmd
2 2
2 1
2 1