#include <cstdio>

using namespace std;
int cdp[1000001], m[8][1000001] ;
int main()
{
    freopen ( "divprim.in","r",stdin ) ;
    freopen ( "divprim.out","w",stdout ) ;
    int t, n, k, lim, j ;
    fscanf ( fin,"%d",&n ) ;
    cdp[0] = cdp[1] = 0 ;
    for ( i = 2 ; i <= 1000000 ; i += 2 )
        cdp[i]++;
    for ( i = 3 ; i <= 1000000 ; i += 2 )
    {
        if ( !cdp[i] )
        {
            for ( j = i ; j <= n ; j += i )
                cdp[i]++;
        }
    }
    i = 0 ;
    for ( j = 1 ; j <= 1000000 ; j ++ )
        m[i][j] = 1 ;
    for ( i = 1 ; i <= 7 ; i ++ )
        for ( j = 1 ; j <= 1000000 ; j ++ )
            if ( cdp[j] == i )
                a[i][j] = j ;
            else
                a[i][j] = a[i][j-1] ;
    for ( i = 1 ; i <= t ; i ++ )
    {
        fscanf ( fin,"%d%d",&n,&k ) ;
        fprintf ( fout,"%d\n",m[k][n] ) ;
    }
    return 0;
}