#include <bits/stdc++.h>
#include <stdio.h>
#include <stdlib.h>
#define MAX 1000000
using namespace std;
FILE *f=fopen("divprim.in","r");
FILE *g=fopen("divprim.out","w");
int sieve[MAX+1],divv[MAX+1],rasp[MAX+1][10],n;
void ciur(){
for(int i=2;i<=MAX;i++){
    if(sieve[i]==0){
        divv[i]++;
        for(int j=2*i;j<=MAX;j+=i){
            sieve[j]=1;
            divv[j]++;
        }
    }
}
}
int main()
{
    ciur();
    rasp[0][0]=1;
    for(int i=1;i<=20;i++){
        for(int j=0;j<=7;j++){
            rasp[i][j]=rasp[i-1][j];
        }
        rasp[i][divv[i]]=i;
    }
    fscanf(f,"%d",&n);
    int a,b;
    for(int i=1;i<=n;i++){
        fscanf(f,"%d%d",&a,&b);
        fprintf(g,"%d\n",rasp[a][b]);
    }
}
/*
10 0
10 1 = 1
10 2
10 3 = 0
10 4
10 5
10 6
10 7
9 = 1

*/