#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <assert.h>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <bitset>

int n, has;

const int maxn =  + ;

int arr[maxn];

LL ans;

LL LCM(LL a, LL b) {

    return a / __gcd(a, b) * b;

}

void dfs(int cur, int sel, LL theLcm) {

    if (theLcm > n) return;

    if (cur == has + ) {

        if (!sel) return;

        if (sel & ) {

            ans += ( << (sel - )) * (n / theLcm);

        } else {

            ans -= ( << (sel - )) * (n / theLcm);

        }

        return;

    }

    dfs(cur + , sel, theLcm);

    dfs(cur + , sel + , LCM(theLcm, arr[cur]));

}

void work() {

    ans = ;

    scanf("%d%d", &n, &has);

    for (int i = ; i <= has; ++i) {

        scanf("%d", &arr[i]);

    }

    dfs(, , );

    cout << ans << endl;

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    int t;

    scanf("%d", &t);

    while (t--) work();

    return ;

}