#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


#include <ext/pb_ds/assoc_container.hpp>
using __gnu_pbds::gp_hash_table;


template <class T> T power(T a, long long e, T m) {
  for (T b = 1; ; (a *= a) %= m) {
    if (e & 1) (b *= a) %= m;
    if (!(e >>= 1)) return b;
  }
}

long long gcd(long long a, long long b) {
  if (a < 0) a = -a;
  if (b < 0) b = -b;
  if (a == 0) return b;
  if (b == 0) return a;
  const int s = __builtin_ctzll(a | b);
  a >>= __builtin_ctzll(a);
  do {
    b >>= __builtin_ctzll(b);
    if (a > b) swap(a, b);
    b -= a;
  } while (b);
  return a << s;
}

bool isPrime(long long n) {
  if (n <= 1 || n % 2 == 0) return (n == 2);
  const int s = __builtin_ctzll(n - 1);
  const long long d = (n - 1) >> s;
  // http://miller-rabin.appspot.com/
  for (const long long base : {2, 325, 9375, 28178, 450775, 9780504, 1795265022}) {
    __int128 a = base % n;
    if (a == 0) continue;
    a = power<__int128>(a, d, n);
    if (a == 1 || a == n - 1) continue;
    bool ok = false;
    for (int i = 0; i < s - 1; ++i) {
      (a *= a) %= n;
      if (a == n - 1) {
        ok = true;
        break;
      }
    }
    if (!ok) return false;
  }
  return true;
}

// n >= 3, odd
void factorizeRec(long long n, vector<long long> &ps) {
  static constexpr int BLOCK = 256;
  if (isPrime(n)) {
    ps.push_back(n);
  } else {
    for (long long c = 2; ; ++c) {
      long long x, y = 2, y0, z = 1, d = 1;
      for (int l = 1; d == 1; l <<= 1) {
        x = y;
        for (int i = 0; i < l; ++i) y = (static_cast<__int128>(y) * y + c) % n;
        for (int i = 0; i < l; i += BLOCK) {
          y0 = y;
          for (int j = 0; j < BLOCK && j < l - i; ++j) {
            y = (static_cast<__int128>(y) * y + c) % n;
            z = (static_cast<__int128>(z) * (y - x)) % n;
          }
          if ((d = gcd(z, n)) != 1) break;
        }
      }
      if (d == n) {
        for (y = y0; ; ) {
          y = (static_cast<__int128>(y) * y + c) % n;
          if ((d = gcd(y - x, n)) != 1) break;
        }
      }
      if (d != n) {
        factorizeRec(d, ps);
        factorizeRec(n / d, ps);
        return;
      }
    }
  }
}

vector<pair<long long, int>> factorize(long long n) {
  vector<pair<long long, int>> pes;
  if (n >= 2) {
    const int s = __builtin_ctzll(n);
    if (s) pes.emplace_back(2, s);
    if (n >> s >= 2) {
      vector<long long> ps;
      factorizeRec(n >> s, ps);
      std::sort(ps.begin(), ps.end());
      const int psLen = ps.size();
      for (int i = 0, j = 0; i < psLen; i = j) {
        for (; j < psLen && ps[i] == ps[j]; ++j) {}
        pes.emplace_back(ps[i], j - i);
      }
    }
  }
  return pes;
}

vector<long long> divisors(long long n) {
  const auto pes = factorize(n);
  vector<long long> ds{1};
  for (const auto &pe : pes) {
    const int len0 = ds.size();
    const int len1 = len0 * (pe.second + 1);
    ds.resize(len1);
    for (int i = len0; i < len1; ++i) ds[i] = ds[i - len0] * pe.first;
  }
  std::sort(ds.begin(), ds.end());
  return ds;
}

////////////////////////////////////////////////////////////////////////////////


constexpr int LIM_SIEVE = (1 << 27) + 1010;
constexpr int LIM_SIEVE_PI = 8'000'000;
int lpf[LIM_SIEVE + 1];
int primesLen;
int primes[LIM_SIEVE_PI];
void sieve() {
  for (int n = 2; n <= LIM_SIEVE; ++n) {
    if (lpf[n] == 0) {
      lpf[n] = n;
      primes[primesLen++] = n;
    }
    for (int i = 0; i < primesLen && primes[i] <= lpf[n] && primes[i] * n <= LIM_SIEVE; ++i) {
      lpf[primes[i] * n] = primes[i];
    }
  }
}


char Ome[LIM_SIEVE + 1];

constexpr int LIM_A = 64;

namespace exper {
constexpr int LIM_N = (1 << 21) + 10;
char ans[LIM_N + 1];
void run() {
  for (int a = 1; a <= LIM_A; ++a) {
    memcpy(ans, Ome, (LIM_N + 1) * sizeof(char));
    for (int src = 2; src <= LIM_N; ++src) {
      queue<pair<int, Int>> que;
      gp_hash_table<Int, int> dist;
      que.emplace(dist[src] = 0, src);
      for (; que.size(); ) {
        const int c = que.front().first;
        const Int u = que.front().second;
        que.pop();
        if (u <= LIM_N) chmin<char>(ans[src], c + ans[u]);
        if (ans[src] <= c + ((u < src) ? ans[u] : 0)) continue;
        auto reach = [&](Int v) -> void {
          if (dist.find(v) != dist.end()) {
            //
          } else {
            que.emplace(dist[v] = c + 1, v);
          }
        };
        if (u <= LIM_SIEVE) {
          for (int uu = u; uu > 1; ) {
            const int p = lpf[uu];
            do { uu /= p; } while (uu % p == 0);
            reach(u / p);
          }
        } else {
          const auto pes = factorize(u);
          for (const auto &pe : pes) reach(u / pe.first);
        }
        reach(a * u + 1);
      }
      if (ans[src] >= 6) {
        printf("%d %d %d\n", a, src, (int)ans[src]);
        fflush(stdout);
      }
    }
    int mx = 0;
    for (int n = 1; n <= LIM_N; ++n) chmax<int>(mx, ans[n]);
    cerr << "a = " << a << ": mx = " << mx << endl;
  }
}

void embed() {
  freopen("E.txt", "r", stdin);
  vector<int> nss[LIM_A + 1];
  for (int a, n, c; ~scanf("%d%d%d", &a, &n, &c); ) {
    assert(c == 6);
    nss[a].push_back(n);
  }
  for (int a = 0; a <= LIM_A; ++a) {
    printf("{");
    for (const int n : nss[a]) printf("%d,", n);
    printf("},\n");
  }
}
}  // exper


const set<int> PRE6[LIM_A + 1] = {
{},
{},
{},
{},
{},
{},
{},
{},
{},
{},
{},
{},
{},
{776576,},
{},
{},
{},
{1091151,1343709,1800063,},
{},
{},
{},
{},
{},
{},
{},
{},
{},
{},
{},
{1273563,1718253,},
{},
{1903993,},
{},
{},
{},
{1607445,},
{},
{},
{},
{},
{},
{1151415,1384047,1436373,},
{},
{1233837,2075949,},
{},
{},
{},
{178929,288603,2045169,},
{},
{634375,},
{},
{},
{},
{720171,905175,1005939,1080675,1180737,1279395,1516995,1597779,1647675,1720251,1858869,},
{},
{},
{},
{},
{},
{441088,686313,950589,1279744,1377536,1629952,1669376,1699072,1972125,1974256,2076416,},
{},
{1180544,1782784,},
{},
{},
{},
};


int M;
vector<int> A;

template <int D> bool able(Int n) {
  if (n <= LIM_SIEVE) {
    if (Ome[n] <= D) return true;
    if (D >= 3) {
      for (int nn = n; nn > 1; ) {
        const int p = lpf[nn];
        do { nn /= p; } while (nn % p == 0);
        if (able<D - 1>(n / p)) return true;
      }
    }
  } else {
    const auto pes = factorize(n);
    for (const auto &pe : pes) if (able<D - 1>(n / pe.first)) return true;
  }
  for (const int a : A) if (able<D - 1>(a * n + 1)) return true;
  return false;
}
template <> bool able<0>(Int n) {
  return (n == 1);
}
template <> bool able<1>(Int n) {
  return (n <= LIM_SIEVE) ? (Ome[n] <= 1) : isPrime(n);
}

int solve(int n) {
  if (A.size() == 1 && PRE6[A[0]].count(n)) return 6;
  if (able<0>(n)) return 0;
  if (able<1>(n)) return 1;
  if (able<2>(n)) return 2;
  if (able<3>(n)) return 3;
  if (able<4>(n)) return 4;
  return 5;
}

int main() {
  sieve();
cerr<<"|primes| = "<<primesLen<<endl;
  for (int n = 2; n <= LIM_SIEVE; ++n) {
    Ome[n] = 1 + Ome[n / lpf[n]];
  }
  
  // exper::run(); return 0;
  // exper::embed(); return 0;
  
  for (int numCases; ~scanf("%d", &numCases); ) { for (int caseId = 1; caseId <= numCases; ++caseId) {
    Int N;
    scanf("%lld%d", &N, &M);
    A.resize(M);
    for (int i = 0; i < M; ++i) {
      scanf("%d", &A[i]);
    }
    
    const int ans = solve(N);
    printf("%d\n", ans);
  }
#ifndef LOCAL
  break;
#endif
  }
  return 0;
}