#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;

const int maxn = 1e6 + 5;

int cnt, prime[maxn];
bool vis[maxn];

void sieve()
{
    cnt = 0;
    for(int i = 2; i < maxn; ++i)
    {
        if(!vis[i])
        {
            prime[++cnt] = i;
        }
        for(int j = 1; j <= cnt && (ll)i * prime[j] < maxn; ++j)
        {
            vis[i * prime[j]] = true;
            if(i % prime[j] == 0) break;
        }
    }
}

int main()
{
    sieve();
    int T;
    scanf("%d", &T);
    while(T--)
    {
        int n, d, q = -1;
        scanf("%d%d", &n, &d);
        int l = 0, r = upper_bound(prime, prime + cnt + 1, d) - prime - 1;
        while(l < r)
        {
            int m = (l + r + 1) >> 1;
            if(((ll)prime[m] * d) >= n) r = m - 1;
            else l = m;
        }
        int ans = l;
        for(int i = 1; i <= l; ++i)
        {
            if(d % prime[i] == 0)
            {
                ans = i;
                break;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}