#include <algorithm>
#include <cstdlib>
#include <climits>
#include <cstring>
#include <cmath>
#include <functional>
#include <utility>

#include <cstdio>
#include <iostream>

#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <map>
#include <list>

#define f first
#define s second
#define mp make_pair
#define pb push_back
#define popb pop_back
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd pair<double,double>
const double PI=acos(-1);

#define for1(i, a, b) for (int i=a; i<=b; i++)
#define rep(i, t) for (int i=0; i<t; i++)
#define RESET(a, b) memset(a, b, sizeof(a))

#define INF 1000000007
#define MOD 1000000007
#define EPS 1e-9

#ifdef _WIN32
#define getchar_unlocked getchar
#endif
template <typename T>
T io(){
	T res=0;
	int sign=1;
	char c;
	while(1){
		c=getchar_unlocked();
		if (c==' '||c=='\t') continue;
		else break;
	}
	res=c-'0';
	while(1){
		c=getchar_unlocked();
		if (c>='0' && c<='9') res=10*res+c-'0';
		else break;
		}
	return res;
	}

void getstr(char* res){
    char c;
    while(1){
        c=getchar_unlocked();
        if(c==' ' || c=='\n') continue;
        else break;
    }
    *res=c; res++;
    while(1){
        c=getchar_unlocked();
        if (c==' ' || c=='\n' || c==EOF) break;
        *res=c; res++;
    }
    *res='\0';
}
using namespace std;

bool isPrime(int n){
	if (n<2) return false;
	if (n==2) return true;
	if(n%2==0) return false;
	for (int i=3;i*i<=n;i++){
		if (n%i==0) return false;
	}
	return true;
}

int main(){
	vector<ll> prime;
	for (int i=2;i<100000;i++){
		if (isPrime(i)) prime.pb(i);
	}
	int tc;
	scanf("%d",&tc);
	while(tc--){
		ll n,k;
		scanf("%lld%lld",&n,&k);
		vector<ll>::iterator count,count1;
		count=upper_bound(prime.begin(),prime.end(),sqrt(n));
		count1=upper_bound(prime.begin(),prime.end(),sqrt(k));
	//	cout<<count-prime.begin()<<" "<<count1-prime.begin()<<endl;
		if (k>n) printf("%lld 0\n",count-prime.begin());
		else printf("%lld %lld\n",count-prime.begin(),(count-prime.begin())-(count1-prime.begin()));
	}
	return 0;
}