/* 
 * File:   main.cpp
 * Author: speedemon
 *
 * Created on September 20, 2009, 12:35 PM
 */
#include <fstream>
#include <cstdlib>

/*
 * 
 */

using namespace std;
ifstream in("divprim.in");
ofstream out("divprim.out");
int main(int argc, char** argv)
{int T,i,max=-1,j;
 int *v,*nrp,*ciur;
    in>>T;
    v=(int*)calloc( T, sizeof(int) );
    nrp=(int*)calloc( T, sizeof(int) );
    for( i=0; i < T; ++i )
    {
        in>>v[i]>>nrp[i];
        if( v[i] > max ) max=v[i];
    }
    ciur=(int*)calloc( max+1, sizeof(int) );
    for( i=2; i <= max; ++i )
        if( !ciur[i] )
        for( j=2; i*j <= max; ++j ) ++ciur[i*j];
    for( i=0; i < T; ++i )
    {
        while( v[i] && nrp[i] != ciur[v[i]] ) --v[i];
        out<<v[i]<<'\n';
    }
    free(v); free(nrp); free(ciur);
    return (EXIT_SUCCESS);
}