#include <fstream>
#include <bitset>
#include <vector>
#define NMAX 1000000

using namespace std;

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

short int grupa[NMAX + 10] ;
int v[10][NMAX], prim[NMAX + 10] , t , x , y;

bitset <NMAX + 10> c;

int caut_bin(int val , int x);

void ciur(){
    c[1] = c[0] = 1;
    for(int i = 2 ; i * i <= NMAX ; ++i){
        if(c[i] == 0){
            for(int j = i * i ; j <= NMAX ; j += i){
                c[j] = 1;
            }
        }
    }
    int k = 0 ;
    for(int i = 1 ; i <= NMAX ; ++i){
        if(c[i] == 0){
            prim[++k] = i;
        }
    }
}

int main()
{
    int ci , p;
    ciur();
    for(int i = 2 ; i <= NMAX ; ++i){
        ci = i ;
        p = 1;
        if(c[ci] == 0){
            grupa[i] = 1;
        }
        else{
            while(prim[p] * prim[p] <= i){
                if(i % prim[p] == 0){
                    if((i / prim[p]) % prim[p] == 0)
                        grupa[i] = grupa[i / prim[p]];
                    else{
                        grupa[i] = grupa[i / prim[p]] + 1;
                    }
                    if(grupa[i] > 8){
                        grupa[i] = 8 ;
                    }
                    break;
                }
                ++p;
            }
        }
    }
    for(int i = 1; i <= NMAX ; ++i){
        v[grupa[i]][++v[grupa[i]][0]] = i;
    }
    f >> t ;
    for(int i = 1 ; i <= t ; ++i){
        f >> x >> y;
        int aux = caut_bin(x , y);
        if(aux == 0)
            g << 0 << '\n';
        else{
            g << v[y][aux] << '\n';
        }
    }
    return 0;
}

int caut_bin(int val, int x){
    int i , p = 0 ;
    for(i = 1 ; i <= v[x][0] ; i *= 2);
    while(i){
        if(p + i <= v[x][0] && v[x][p + i] <= val){
            p += i;
        }
        i /= 2;
    }
    return p;
}