#include <bits/stdc++.h>
#define Nmax 1000005
using namespace std;
int n, k, sol;
short ciur[Nmax];
void eratostene()
{
    ciur[0] = ciur[1] = 0;
    for(int i = 2; i <= Nmax; i +=2)
    {
        ciur[i] = 1;
    }
    for(int i = 3; i <= Nmax; i += 2)
    {
        if(!ciur[i])
        {
            for(int j = i; j <= Nmax; j = j + i)
            {
                ciur[j]++;
            }
        }
    }
}
class InParser {
    vector<char> str;
    int ptr;
    ifstream fin;

    char getChar() {
        if (ptr == int(str.size())) {
            fin.read(str.data(), str.size());
            ptr = 0;
        }
        return str[ptr++];
    }

    template<class T>
    T getInt() {
        char chr = getChar();
        while (!isdigit(chr) && chr != '-')
            chr = getChar();
        int sgn = +1;
        if (chr == '-') {
            sgn = -1;
            chr = getChar();
        }
        T num = 0;
        while (isdigit(chr)) {
            num = num * 10 + chr - '0';
            chr = getChar();
        }
        return sgn * num;
    }

public:
    InParser(const char* name) : str(1e5), ptr(str.size()), fin(name) { }
    ~InParser() { fin.close(); }

    template<class T>
    friend InParser& operator>>(InParser& in, T& num) {
        num = in.getInt<T>();
        return in;
    }
};
int t;
InParser fin("divprim.in");
ofstream fout("divprim.out");
int main()
{
    eratostene();
    fin >> t;
    for(int i = 1; i <= t; ++i)
    {
    fin >> n >> k;
    int st = 1, dr = n, mid, sol = 0;
    while(st <= dr)
    {
        mid = st + (dr - st) / 2;
        if(ciur[mid] == k)
        {
            sol = mid;
            st = mid + 1;
        }
        else
        {
            dr = mid - 1;
        }
    }
    fout << sol;
    }
    return 0;
}