import java.io.File;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.*;

public class Main_Prime_Darts_13245 {

    static int dp[], fail = -1 >>> 5;
    static List<Integer> list = new ArrayList<Integer>();

    static int rec(int p[], int v) {
        for (int i = 1; i < dp.length; i++) {
            dp[i] = fail;
        }
        for (int i = 0; i <= v; i++) {
            for (int j = 0; j < p.length; j++) {
                if (p[j] <= i) {
                    int sub = dp[i - p[j]];
                    if (sub != fail && sub + 1 < dp[i]) {
                        dp[i] = sub + 1;
                    }
                }
            }
        }
        return dp[v];
    }

    static int rec2(int[] p, int v){
        if (dp[v] != fail) return dp[v];

        for (int prime : p) {
            if (v >= prime) {
                dp[v] = 1+ ( rec2(p, v - prime));
            }
        }



        return dp[v];
    }

    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(new File("input.txt"));
        PrintWriter out = new PrintWriter(System.out);
        Primes.sieve();
        int tc = in.nextInt();
        while (tc-- > 0) {
            int size = in.nextInt();
            int sum = in.nextInt();
            int[] prime = new int[list.size()];
            for (int i = 0; i < prime.length; i++) {
                prime[i] = list.get(i);
            }
            int[] p = Arrays.copyOf(prime, size);
            dp = new int[sum + 1];
            Arrays.fill(dp, fail);
            dp[0] = 0;
            out.println(rec2(p, sum));
        }
        out.flush();
    }

    static class Primes {

        static BitSet bset;
        static int MAX = 50000;

        public static void sieve() {
            bset = new BitSet(MAX);
            list.add(1);
            bset.set(2);
            list.add(2);
            for (int j = 3; j < MAX; j += 2) {
                bset.set(j);
            }
            int sqrt = (int) Math.sqrt(MAX);
            for (int i = 3; i < sqrt; i += 2) {
                if (bset.get(i)) {
                    for (int j = i * i; j < MAX; j += 2 * i) {
                        bset.clear(j);
                    }
                    list.add(i);
                }
            }
        }
        //long values start from 4422

        public static boolean isPrime(long n) { // n>=0
            if (n < MAX) {
                return bset.get((int) n);
            }
            int sqrt = (int) Math.sqrt(n);
            for (int i = 2; i <= sqrt; i = bset.nextSetBit(i + 1)) {
                if (n % i == 0) {
                    return false;
                }
            }
            return true;
        }
    }

}