#include <fstream>
#include <cmath>
using namespace std;
short v[1000001];
int  a[8][1000001];
void completam(int i)
{
    int j;
    for(j=i;j<=1000000;j+=i)
    {
        v[j]+=1;
        //a[v[j]][j]=j;
    }
}
int main()
{
    ifstream f("divprim.in");
    ofstream g("divprim.out");
    int t,n,k,r,i,j;
    //r=1000;
    completam(2);
    for(i=3;i<=500000;i+=2)
    {
        if(v[i]==0)
            completam(i);
    }
    for(i=500001;i<=1000000;i+=2)
     {
         if(v[i]==0)
            v[i]=1;
      //  a[v[i]][i]=i;
     }
     for(i=1;i<=1000000;i++)
     {
         for(j=1;j<=7;j++)
            a[j][i]=a[j][i-1];
         a[v[i]][i]=i;

     }
       for(i=1;i<=7;i++)
    {
        for(j=1;j<=40;j++)
            g<<a[i][j]<<" ";
        g<<'\n';
    }
    f>>t;
    for(i=1;i<=t;i++)
    {
        f>>n>>k;
        g<<a[k][n]<<'\n';
    }

    f.close();
    g.close();
    return 0;
}