/*
ID: jsnjhcb1
PROG: d
LANG: C++
*/
/*************************************************************************
    > File Name: d.cpp
    > Author: UCU
    > Mail: jsnjhcb@icloud.com
    > Created Time: 六  7/23 19:36:59 2016
 ************************************************************************/

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<string>
#include<cstdlib>
#include<queue>
#include<cmath>
#include<iomanip>
#include<climits>
#include<fstream>
using namespace std;
#define maxn 100000
bool isprime[maxn+10];
int pricnt;
int prime[maxn];
void init(){
    memset(isprime,true,sizeof isprime);
    isprime[0] = isprime[1] = false;
    pricnt = 0;
    for(int i=2;i<=maxn;++i){
        if(isprime[i]){
            prime[pricnt++] = i;
            for(int j=i<<1;j<=maxn;j+=i){
                isprime[j] = false;
            }
        }
    }
}
int main(){
    int T;
    init();
    scanf("%d",&T);
    while(T--){
        int n,d;
        scanf("%d%d",&n,&d);
        int minprime = -1;
        int cnt = 0;
        int key = n / d;
        int l = 0, r = pricnt;
        int ans2 = -1;
        while(l <= r){
            int mid = (l + r) / 2;
            if(prime[mid] <= key){
                ans2 = mid;
                l = mid + 1;
            }
            else{
                r = mid - 1;
            }
        }
        for(int i=0;i<pricnt && i<=ans2;++i){
            if(d % prime[i] == 0){
                cnt = i;
                minprime = prime[i];
                break;
            }
        }
        int ans = ans2 + 1;
        if(minprime != -1){
            ans = min(ans , cnt + 1);
        }
        printf("%d\n",ans);
    }
    return 0;
}