const   fin = 'divprim.in'; fout = 'divprim.out'; max = 1000 * 1000;

type
        tabelprime = array[1..max] of boolean;
        tabelprim  = array[1..78498] of longword;
        tabeldiviz = array[1..max] of word;
        solutiontemp = array[0..7] of longword;
        solution = array[1..max] of solutiontemp;
var
        p : tabelprime;
        prim : tabelprim;
        diviz : tabeldiviz;
        stemp : solutiontemp;
        s : solution;

procedure prime();
var
        i ,j ,x : longword;
begin
        i := 1;
        p[i] := true;
        x := trunc(sqrt(max));
        while (i <= x) do
        begin
                repeat  i := i + 1; until not p[i];
                j := i * i;
                while (j <= max) do
                begin
                        p[j] := true;
                        j := j + i;
                end;
        end;
        x := 0;
        for i := 2 to max do
        if not p[i] then
        begin
                x := x + 1;
                prim[x] := i;
        end;
end;

function divizori(n : longword) : byte;
var
        i : longword;
        x : byte;
begin
        x := 0;
        i := 1;
        while (n > 1) do
        begin
                if not p[n] then
                begin
                        x := x + 1;
                        break;
                end;
                while (n mod prim[i] <> 0) do i := i + 1;
                while (n mod prim[i] = 0) do n := n div prim[i];
                x := x + 1;
        end;
        divizori := x;
end;

procedure makesolution();
var
        i : longword;
begin
        for i := 1 to max do
        begin
                if (diviz[i] <= 7) then stemp[diviz[i]] := i;
                s[i] := stemp;
        end;
end;

procedure main();
var
        n ,i ,x ,k : longword;
begin
        assign(input , fin); reset(input);
        assign(output , fout); rewrite(output);

        prime();

        for i := 2 to max do diviz[i] := divizori(i);

        makesolution();

        readln(n);
        for i := 1 to n do
        begin
                readln(x, k);
                write(s[x][k],#10);
        end;
end;

begin
        main();
end.