#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;
}