#include <bits/stdc++.h>

using namespace std;
using ll = long long;
ll result = 0;
void Try(int pos, vector <ll> a,ll n, int m, ll res, ll d, vector <ll> &b)
{
    for (int i = pos; i < m; i++)
    {
        if (res + d < b[i]) continue;
        if (n % a[i] == 0 && n != a[i])
        {
            b[i] = max(b[i],res + d);
            Try(i + 1,a,a[i],m,res + d, d * n / a[i],b);
        }
    }
    result = max(result,res);
}
int main()
{
    long long q,n,m; cin >> q;
    for (int i = 0; i < q; i++)
    {
        cin >> n >> m;
        vector <ll> a(m);
        vector <ll> b(m);
        for (int i = 0; i < m; i++)
        {
            cin >> a[i];
            b[i] = 0;
        }
        sort(a.begin(),a.end(),greater<ll>());
        Try(0,a,n,m,0,1,b);
        cout << result << endl;
        result = 0;
    }
    return 0;
}

function stoneDivision(n: number, s: number[]): number {
    /**
     * Build a recursion function that have
     * 
     * + number [n] is size of a pile
     * + number [s] is set of divider
     * -> return 0 if [n] can't be divided by any of [s]
     *  * recursion mean this couple can't be go furthur
     * -> return 1 if [n] can divided
     *  * number [d] is a number in [s] that fit conditions
     *  * number [n] can be divided multiple times, so multiply by [n]/[d]
     *  * recursion mean this couple is nice, plus
     */

    const memo: { [key: string]: number } = {}
    const recurse = (n: number): number => {
        if (n in memo) return memo[n]

        let max = 0
        for (let d of s) {
            if (d != n && n % d == 0) {
                max = Math.max(max, 1 + (n / d) * recurse(d))
            }
        }

        return memo[n] = max
    }

    return recurse(n)
}

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();
    }
}

Your Output (stdout)
    29
Debug output
    29
    0
    1
    31