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

class Result {

    // Memoization table
    private static Map<Long, Long> memo = new HashMap<>();

    // Method to perform stone division
    public static long stoneDivision(long n, List<Long> s) {
        // If the number of stones is 1 or no valid divisor exists, no further splits are possible
        if (n == 1) {
            return 0;
        }

        // If we've already computed the result for this number of stones, return it
        if (memo.containsKey(n)) {
            return memo.get(n);
        }

        long maxMoves = 0;
        boolean validSplit = false;

        // Try to split the pile using each number in S
        for (long x : s) {
            if (n % x == 0 && n != x) {  // Ensure we only divide when n > x to prevent infinite recursion
                validSplit = true;
                long numOfPiles = n / x;
                // One move for splitting and then recursively process the smaller piles
                long moves = numOfPiles * stoneDivision(x, s) + 1;
                maxMoves = Math.max(maxMoves, moves);
            }
        }

        // If no valid splits are possible, return 0 moves
        if (!validSplit) {
            memo.put(n, 0L);
            return 0L;
        }

        // Store the result in memoization table and return
        memo.put(n, maxMoves);
        return maxMoves;
    }

    // Method to clear memoization table
    public static void clearMemo() {
        memo.clear();
    }
}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

        int q = Integer.parseInt(bufferedReader.readLine().trim());

        for (int qItr = 0; qItr < q; qItr++) {
            String[] firstMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");

            long n = Long.parseLong(firstMultipleInput[0]);

            int m = Integer.parseInt(firstMultipleInput[1]);

            String[] sTemp = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");

            List<Long> s = new ArrayList<>();

            for (int i = 0; i < m; i++) {
                long sItem = Long.parseLong(sTemp[i]);
                s.add(sItem);
            }

            // Clear memoization table before processing a new query
            Result.clearMemo();

            long result = Result.stoneDivision(n, s);

            bufferedWriter.write(String.valueOf(result));
            bufferedWriter.newLine();
        }

        bufferedReader.close();
        bufferedWriter.close();
    }
}