import java.io.*;
import java.util.Scanner;

public class Main {

  public static void main(String[] args) throws IOException {
    int t, n, k, nr;

    Scanner scanner = new Scanner(new BufferedReader(new FileReader("divprim.in")));
    BufferedWriter bw = new BufferedWriter(new FileWriter("divprim.out"));
    t = scanner.nextInt();
    for (int j = 0; j < t; j++) {
      n = scanner.nextInt();
      k = scanner.nextInt();
      nr = 0;

      for (int i = n; i > 0; i--) {
        if (getNrOfDivisors(i) == k) {
          nr = i;
          break;
        }
      }
      bw.write(nr + "\n");
    }
    bw.close();
  }

  public static int getNrOfDivisors(int n) {
    int i = 2;
    int nr = 0;
    int tmp = n;
    while (n > i) {
      if (n % i == 0) {
        nr++;
        while (n % i == 0) {
          n = n / i;
        }
      }
      i++;
    }
    if (tmp != n && n != 1) {
      nr++;
    }
    return nr;
  }
}