#include <algorithm>
#include <fstream>

using namespace std;

ifstream in("divprim.in");
ofstream out("divprim.out");

#define T 100005
#define N 1000005

struct query
{
    int n, poz;
    char k;
};

int t;
char v[N];
int d[N];
int rez[T];
query a[T];

inline int cmp(query q1, query q2)
{
    return q1.k < q2.k;
}

int main()
{
    in >> t;

    for(int i = 2; i <= N; i += 2)
        v[i]++;

    for(int i = 3; i <= N; i += 2)
        if(v[i] == 0)
            for(int j = i; j <= N; j += i)
                v[j]++;

    for(int i = 1; i <= t; i++)
    {
        in >> a[i].n >> a[i].k;
        a[i].k -= '0';
        a[i].poz = i;
    }

    sort(a + 1, a + t + 1, cmp);

    int curent = 1;
    for(int i = 0; i <= 7; i++)
    {
        int nr = 0;
        for(int j = 1; j <= N; j++)
            if(v[j] == i)
                d[++nr] = j;

        while(a[curent].k == i)
        {
            int n = a[curent].n;
            int j = 0, pas = (1 << 19);
            while(pas)
            {
                if(j + pas <= nr && d[j + pas] <= n)
                    j += pas;
                pas >>= 1;
            }

            rez[a[curent].poz] = d[j];
            curent++;
        }
    }

    for(int i = 1; i <= t; i++)
        out << rez[i] << '\n';
    return 0;
}