#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
#define all(x) x.begin(),x.end()
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;
const int N=1e6+5,M=1.5e8+5,K=1000+5,mod=998244353,Mod=mod-1;const db eps=1e-8;const int INF=1e9+7;mt19937 rnd(263082);
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
namespace Debug{
Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
#ifdef LOCAL
#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
#else
#define gdb(...) void()
#endif
}using namespace Debug;
#undef Tp
int n,m,A[10],lim;const int k=1.5e8;
int pr[M/10],ph,La[M];bitset<M> flag;
ll f[1000],g[1000];int fh,gh;
#ifndef __OY_FASTIO__
#define __OY_FASTIO__
#ifndef INPUT_FILE
#define INPUT_FILE "in.txt"
#endif
#ifndef OUTPUT_FILE
#define OUTPUT_FILE "out.txt"
#endif
namespace OY {
namespace IO {
using size_type = size_t;
static constexpr size_type INPUT_BUFFER_SIZE = 1 << 16, OUTPUT_BUFFER_SIZE = 1 << 16, MAX_INTEGER_SIZE = 20, MAX_FLOAT_SIZE = 50;
#ifdef OY_LOCAL
static constexpr char input_file[] = INPUT_FILE, output_file[] = OUTPUT_FILE;
#else
static constexpr char input_file[] = "", output_file[] = "";
#endif
struct InputHelper {
FILE *m_file_ptr;
char m_buf[INPUT_BUFFER_SIZE], *m_end, *m_cursor;
bool m_ok;
InputHelper &set_bad() { return m_ok = false, *this; }
template <size_type BlockSize>
void _reserve() {
size_type a = m_end - m_cursor;
if (a >= BlockSize) return;
memmove(m_buf, m_cursor, a), m_cursor = m_buf;
size_type b = a + fread(m_buf + a, 1, INPUT_BUFFER_SIZE - a, m_file_ptr);
if (b < INPUT_BUFFER_SIZE) m_end = m_buf + b, *m_end = EOF;
}
template <typename Tp, typename BinaryOperation>
InputHelper &fill_integer(Tp &ret, BinaryOperation op) {
if (!isdigit(*m_cursor)) return set_bad();
ret = op(Tp(0), *m_cursor - '0');
size_type len = 1;
while (isdigit(*(m_cursor + len))) ret = op(ret * 10, *(m_cursor + len++) - '0');
m_cursor += len;
return *this;
}
explicit InputHelper(const char *inputFileName) : m_ok(true), m_cursor(m_buf + INPUT_BUFFER_SIZE), m_end(m_buf + INPUT_BUFFER_SIZE) { m_file_ptr = *inputFileName ? fopen(inputFileName, "rt") : stdin; }
~InputHelper() { fclose(m_file_ptr); }
static InputHelper &get_instance() {
static InputHelper s_obj(input_file);
return s_obj;
}
static bool is_blank(char c) { return c == ' ' || c == '\t' || c == '\n' || c == '\r'; }
static bool is_endline(char c) { return c == '\n' || c == EOF; }
const char &getchar_checked() {
_reserve<1>();
return *m_cursor;
}
const char &getchar_unchecked() const { return *m_cursor; }
void next() { ++m_cursor; }
template <typename Tp, typename std::enable_if<std::is_signed<Tp>::value & std::is_integral<Tp>::value>::type * = nullptr>
InputHelper &operator>>(Tp &num) {
while (is_blank(getchar_checked())) next();
_reserve<MAX_INTEGER_SIZE>();
if (getchar_unchecked() != '-') return fill_integer(num, std::plus<Tp>());
next();
return fill_integer(num, std::minus<Tp>());
}
template <typename Tp, typename std::enable_if<std::is_unsigned<Tp>::value & std::is_integral<Tp>::value>::type * = nullptr>
InputHelper &operator>>(Tp &num) {
while (is_blank(getchar_checked())) next();
_reserve<MAX_INTEGER_SIZE>();
return fill_integer(num, std::plus<Tp>());
}
template <typename Tp, typename std::enable_if<std::is_floating_point<Tp>::value>::type * = nullptr>
InputHelper &operator>>(Tp &num) {
bool neg = false, integer = false, decimal = false;
while (is_blank(getchar_checked())) next();
_reserve<MAX_FLOAT_SIZE>();
if (getchar_unchecked() == '-') {
neg = true;
next();
}
if (!isdigit(getchar_unchecked()) && getchar_unchecked() != '.') return set_bad();
if (isdigit(getchar_unchecked())) {
integer = true;
num = getchar_unchecked() - '0';
while (next(), isdigit(getchar_unchecked())) num = num * 10 + (getchar_unchecked() - '0');
}
if (getchar_unchecked() == '.')
if (next(), isdigit(getchar_unchecked())) {
if (!integer) num = 0;
decimal = true;
Tp unit = 0.1;
num += unit * (getchar_unchecked() - '0');
while (next(), isdigit(getchar_unchecked())) num += (unit *= 0.1) * (getchar_unchecked() - '0');
}
if (!integer && !decimal) return set_bad();
if (neg) num = -num;
return *this;
}
InputHelper &operator>>(char &c) {
while (is_blank(getchar_checked())) next();
if (getchar_checked() == EOF) return set_bad();
c = getchar_checked(), next();
return *this;
}
InputHelper &operator>>(std::string &s) {
while (is_blank(getchar_checked())) next();
if (getchar_checked() == EOF) return set_bad();
s.clear();
do {
s += getchar_checked();
next();
} while (!is_blank(getchar_checked()) && getchar_unchecked() != EOF);
return *this;
}
explicit operator bool() { return m_ok; }
};
struct OutputHelper {
FILE *m_file_ptr = nullptr;
char m_buf[OUTPUT_BUFFER_SIZE], *m_end, *m_cursor;
char m_temp_buf[MAX_FLOAT_SIZE], *m_temp_buf_cursor, *m_temp_buf_dot;
uint64_t m_float_reserve, m_float_ratio;
void _write() { fwrite(m_buf, 1, m_cursor - m_buf, m_file_ptr), m_cursor = m_buf; }
template <size_type BlockSize>
void _reserve() {
size_type a = m_end - m_cursor;
if (a >= BlockSize) return;
_write();
}
OutputHelper(const char *outputFileName, size_type prec = 6) : m_cursor(m_buf), m_end(m_buf + OUTPUT_BUFFER_SIZE), m_temp_buf_cursor(m_temp_buf) { m_file_ptr = *outputFileName ? fopen(outputFileName, "wt") : stdout, precision(prec); }
static OutputHelper &get_instance() {
static OutputHelper s_obj(output_file);
return s_obj;
}
~OutputHelper() { flush(), fclose(m_file_ptr); }
void precision(size_type prec) { m_float_reserve = prec, m_float_ratio = uint64_t(pow(10, prec)), m_temp_buf_dot = m_temp_buf + prec; }
OutputHelper &flush() { return _write(), fflush(m_file_ptr), *this; }
void putchar(const char &c) {
if (m_cursor == m_end) _write();
*m_cursor++ = c;
}
template <typename Tp, typename std::enable_if<std::is_signed<Tp>::value & std::is_integral<Tp>::value>::type * = nullptr>
OutputHelper &operator<<(Tp ret) {
_reserve<MAX_INTEGER_SIZE>();
size_type len = 0;
if (ret >= 0)
do *(m_cursor + len++) = '0' + ret % 10, ret /= 10;
while (ret);
else {
putchar('-');
do *(m_cursor + len++) = '0' - ret % 10, ret /= 10;
while (ret);
}
for (size_type i = 0, j = len - 1; i < j;) std::swap(*(m_cursor + i++), *(m_cursor + j--));
m_cursor += len;
return *this;
}
template <typename Tp, typename std::enable_if<std::is_unsigned<Tp>::value & std::is_integral<Tp>::value>::type * = nullptr>
OutputHelper &operator<<(Tp ret) {
_reserve<MAX_INTEGER_SIZE>();
size_type len = 0;
do *(m_cursor + len++) = '0' + ret % 10, ret /= 10;
while (ret);
for (size_type i = 0, j = len - 1; i < j;) std::swap(*(m_cursor + i++), *(m_cursor + j--));
m_cursor += len;
return *this;
}
template <typename Tp, typename std::enable_if<std::is_floating_point<Tp>::value>::type * = nullptr>
OutputHelper &operator<<(Tp ret) {
if (ret < 0) {
putchar('-');
return *this << -ret;
}
ret *= m_float_ratio;
uint64_t integer = ret;
if (ret - integer >= 0.4999999999) integer++;
do {
*m_temp_buf_cursor++ = '0' + integer % 10;
integer /= 10;
} while (integer);
if (m_temp_buf_cursor > m_temp_buf_dot) {
do putchar(*--m_temp_buf_cursor);
while (m_temp_buf_cursor > m_temp_buf_dot);
putchar('.');
} else {
putchar('0'), putchar('.');
for (size_type i = m_temp_buf_dot - m_temp_buf_cursor; i--;) putchar('0');
}
do putchar(*--m_temp_buf_cursor);
while (m_temp_buf_cursor > m_temp_buf);
return *this;
}
OutputHelper &operator<<(const char &ret) {
putchar(ret);
return *this;
}
OutputHelper &operator<<(const char *ret) {
while (*ret) putchar(*ret++);
return *this;
}
OutputHelper &operator<<(const std::string &ret) { return *this << ret.data(); }
};
InputHelper &getline(InputHelper &ih, std::string &line) {
line.clear();
if (ih.getchar_checked() == EOF) return ih.set_bad();
while (!InputHelper::is_endline(ih.getchar_checked())) line += ih.getchar_unchecked(), ih.next();
if (ih.getchar_unchecked() != EOF) ih.next();
return ih;
}
}
}
using OY::IO::getline;
#endif
#ifndef __OY_PRIMECHECK0__
#define __OY_PRIMECHECK0__
#ifdef _MSC_VER
#endif
namespace OY {
bool is_prime32(uint32_t n) {
if (n < 64) return 0x28208a20a08a28ac >> n & 1;
if (n % 2 == 0 || n % 3 == 0 || n % 5 == 0 || n % 7 == 0) return false;
struct Info {
uint32_t m_mod, m_mod2, m_pinv, m_ninv;
uint32_t m_one;
uint64_t m_inv;
void set_mod(uint32_t P) {
m_mod = m_pinv = P, m_mod2 = P * 2, m_ninv = -uint64_t(P) % P, m_inv = uint64_t(-1) / P + 1;
for (size_t i = 0; i != 4; i++) m_pinv *= uint32_t(2) - mod() * m_pinv;
m_pinv = -m_pinv, m_one = strict_reduce(raw_init(1));
}
uint32_t mod(uint64_t val) const {
#ifdef _MSC_VER
uint64_t x;
_umul128(val, m_inv, &x);
uint32_t res = val - x * mod();
#else
uint32_t res = val - uint64_t((__uint128_t(val) * m_inv) >> 64) * mod();
#endif
if (res >= mod()) res += mod();
return res;
}
uint32_t mod() const { return m_mod; }
uint32_t reduce(uint64_t val) const { return (val + uint64_t(uint32_t(val) * m_pinv) * mod()) >> 32; }
uint32_t strict_reduce(uint32_t val) const { return val >= mod() ? val - mod() : val; }
uint32_t mul(uint32_t a, uint32_t b) const { return reduce(uint64_t(a) * b); }
uint32_t pow(uint32_t a, uint32_t n) const {
uint32_t res = one(), b = a;
while (n) {
if (n & 1) res = mul(res, b);
b = mul(b, b), n >>= 1;
}
return res;
}
uint32_t one() const { return m_one; }
uint32_t raw_init(uint32_t val) const { return mul(val, m_ninv); }
};
Info info;
info.set_mod(n);
uint32_t d = (n - 1) >> std::countr_zero(n - 1), one = info.one(), minus_one = info.mod() - one;
auto mr = [&](uint32_t a) {
uint32_t s = d, y = info.pow(info.raw_init(a), s);
while (s != n - 1 && info.strict_reduce(y) != one && info.strict_reduce(y) != minus_one) y = info.mul(y, y), s <<= 1;
return info.strict_reduce(y) == minus_one || s % 2;
};
return mr(2) && mr(7) && mr(61);
}
bool is_prime64(uint64_t n) {
if (n < 64) return 0x28208a20a08a28ac >> n & 1;
if (n % 2 == 0 || n % 3 == 0 || n % 5 == 0 || n % 7 == 0) return false;
struct Info {
uint64_t m_mod, m_mod2, m_pinv, m_ninv, m_inv, m_one;
void set_mod(uint64_t P) {
#ifdef _MSC_VER
uint64_t high, low;
low = _umul128(-P % P, -P % P, &high);
_udiv128(high, low, P, &m_ninv);
#else
m_ninv = -__uint128_t(P) % P;
#endif
m_mod = m_pinv = P, m_mod2 = P * 2, m_inv = uint64_t(-1) / P + 1;
for (size_t i = 0; i != 5; i++) m_pinv *= uint64_t(2) - mod() * m_pinv;
m_pinv = -m_pinv, m_one = strict_reduce(raw_init(1));
}
uint64_t mod(uint64_t val) const {
#ifdef _MSC_VER
uint64_t res;
_umul128(val, m_inv, &res);
res = val - res * mod();
#else
uint64_t res = val - uint64_t((__uint128_t(val) * m_inv) >> 64) * mod();
#endif
if (res >= mod()) res += mod();
return res;
}
uint64_t mod() const { return m_mod; }
#ifdef _MSC_VER
uint64_t reduce(uint64_t high, uint64_t low) const {
uint64_t _, res, low2 = _umul128(_umul128(low, m_pinv, &_), mod(), &res);
return res + high + (low2 > -low || (low2 == -low && low));
#else
uint64_t reduce(__uint128_t val) const {
return (val + __uint128_t(uint64_t(val) * m_pinv) * mod()) >> 64;
#endif
}
uint64_t strict_reduce(uint64_t val) const { return val >= mod() ? val - mod() : val; }
uint64_t mul(uint64_t a, uint64_t b) const {
#ifdef _MSC_VER
uint64_t high, low;
low = _umul128(a, b, &high);
return reduce(high, low);
#else
return reduce(__uint128_t(a) * b);
#endif
}
uint64_t pow(uint64_t a, uint64_t n) const {
uint64_t res = one(), b = a;
while (n) {
if (n & 1) res = mul(res, b);
b = mul(b, b), n >>= 1;
}
return res;
}
uint64_t one() const { return m_one; }
uint64_t raw_init(uint64_t val) const { return mul(val, m_ninv); }
};
Info info;
info.set_mod(n);
uint64_t d = (n - 1) >> std::countr_zero(n - 1), one = info.one(), minus_one = info.mod() - one;
auto mr = [&](uint32_t a) {
if (a >= n) return true;
uint64_t s = d, y = info.pow(info.raw_init(a), s);
while (s != n - 1 && info.strict_reduce(y) != one && info.strict_reduce(y) != minus_one) y = info.mul(y, y), s <<= 1;
return info.strict_reduce(y) == minus_one || s % 2;
};
if (!(n >> 32)) return mr(2) && mr(7) && mr(61);
return mr(2) && mr(325) && mr(9375) && mr(28178) && mr(450775) && mr(9780504) && mr(1795265022);
}
template <typename Tp>
bool is_prime(Tp n) {
if constexpr (std::is_same<Tp, uint32_t>::value)
return is_prime32(n);
else
return is_prime64(n);
}
}
#endif
#ifndef __OY_POLLARDRHO__
#define __OY_POLLARDRHO__
namespace OY {
namespace PollardRho {
static constexpr size_t batch = 8192;
struct PollardRhoPair {
uint64_t m_prime;
uint32_t m_count;
bool operator<(const PollardRhoPair &rhs) const { return m_prime < rhs.m_prime; }
};
uint64_t pick(uint64_t n) {
if (n % 2 == 0) { return 2; }
struct Info {
uint64_t m_mod, m_pinv;
void set_mod(uint64_t n) {
m_mod = m_pinv = n;
for (size_t i = 0; i < 5; ++i) m_pinv *= 2 - m_mod * m_pinv;
}
uint64_t mul_add(uint64_t a, uint64_t b, uint64_t c) const {
#ifdef _MSC_VER
uint64_t high, low, _, res;
low = _umul128(a, b, &high);
_umul128(_umul128(low, m_pinv, &_), m_mod, &res);
return c + m_mod + high - res;
#else
__uint128_t d = __uint128_t(a) * b;
return c + m_mod + (d >> 64) - uint64_t((__uint128_t(uint64_t(d) * m_pinv) * m_mod) >> 64);
#endif
}
uint64_t mul(uint64_t a, uint64_t b) const { return mul_add(a, b, 0); }
};
Info info;
info.set_mod(n);
uint64_t C1 = 1, C2 = 2, M = 1024, Z1 = 1, Z2 = 2, ans = 0;
auto find = [&]() {
uint64_t z1 = Z1, z2 = Z2;
for (uint64_t k = M;; k *= 2) {
uint64_t x1 = z1 + n, x2 = z2 + n;
for (uint64_t j = 0; j < k; j += M) {
uint64_t y1 = z1, y2 = z2, q1 = 1, q2 = 2;
z1 = info.mul_add(z1, z1, C1), z2 = info.mul_add(z2, z2, C2);
for (uint64_t i = 0; i < M; ++i) {
uint64_t t1 = x1 - z1, t2 = x2 - z2;
z1 = info.mul_add(z1, z1, C1), z2 = info.mul_add(z2, z2, C2);
q1 = info.mul(q1, t1), q2 = info.mul(q2, t2);
}
q1 = info.mul(q1, x1 - z1), q2 = info.mul(q2, x2 - z2);
uint64_t q3 = info.mul(q1, q2), g3 = std::gcd(n, q3);
if (g3 == 1) continue;
if (g3 != n) return void(ans = g3);
uint64_t g1 = std::gcd(n, q1), g2 = std::gcd(n, q2), C = g1 != 1 ? C1 : C2, x = g1 != 1 ? x1 : x2, z = g1 != 1 ? y1 : y2, g = g1 != 1 ? g1 : g2;
if (g == n)
do z = info.mul_add(z, z, C), g = std::gcd(n, x - z);
while (g == 1);
if (g != n) return void(ans = g);
Z1 += 2, Z2 += 2;
return;
}
}
};
do find();
while (!ans);
return ans;
}
template <typename Callback>
void _dfs(uint64_t cur, Callback &&call) {
if (!is_prime(cur)) {
uint64_t a = pick(cur);
_dfs(a, call), _dfs(cur / a, call);
} else
call(cur);
}
template <typename Callback>
void enumerate_prime_factors(uint64_t n, Callback &&call) {
if (n % 2 == 0) {
uint32_t ctz = std::countr_zero(n);
n >>= ctz;
while (ctz--) call(uint64_t(2));
}
if (n > 1) _dfs(n, call);
}
template <bool Sorted = false>
std::vector<PollardRhoPair> decomposite(uint64_t n) {
std::vector<PollardRhoPair> res;
if (n % 2 == 0) {
uint32_t ctz = std::countr_zero(n);
res.push_back({uint64_t(2), ctz}), n >>= ctz;
}
auto call = [&](uint64_t x) {
auto find = std::find_if(res.begin(), res.end(), [&](const PollardRhoPair &p) { return p.m_prime == x; });
if (find == res.end())
res.push_back({x, 1});
else
find->m_count++;
};
if (n > 1) _dfs(n, call);
if constexpr (Sorted) std::sort(res.begin(), res.end());
return res;
}
template <typename Callback>
void _dfs(uint32_t index, uint64_t prod, const std::vector<PollardRhoPair> &pairs, Callback &&call) {
if (index == pairs.size())
call(prod);
else {
auto &&pair = pairs[index];
uint64_t p = pair.m_prime, c = pair.m_count;
_dfs(index + 1, prod, pairs, call);
while (c--) _dfs(index + 1, prod *= p, pairs, call);
}
}
template <typename Callback>
void enumerate_factors(const std::vector<PollardRhoPair> &pairs, Callback &&call) { _dfs(0, 1, pairs, call); }
template <bool Sorted = false>
std::vector<uint64_t> get_factors(uint64_t n) {
std::vector<uint64_t> res;
uint32_t count = 1;
auto pairs = decomposite<false>(n);
for (auto &&pair : pairs) count *= pair.m_count + 1;
res.reserve(count);
enumerate_factors(pairs, [&](uint64_t f) { res.push_back(f); });
if constexpr (Sorted) std::sort(res.begin(), res.end());
return res;
}
uint64_t get_Euler_Phi(uint64_t n) {
for (const auto &pair : decomposite(n)) n = n / pair.m_prime * (pair.m_prime - 1);
return n;
}
}
}
#endif
ll st[N];
int sh;
void calcs(ll n){
sh=0;
OY::PollardRho::enumerate_prime_factors(n, [&](auto p) {
st[++sh]=p;
});
}
void Solve(){
int i,j;scanf("%d%d",&n,&m);
for(i=1;i<=m;i++) scanf("%d",&A[i]);
calcs(n);lim=sh;f[fh=1]=n;
for(int T=1;T+1<lim;T++){
sort(f+1,f+fh+1);
fh=unique(f+1,f+fh+1)-f-1;
gh=fh;copy(f+1,f+fh+1,g+1);fh=0;
for(int i=1;i<=gh&&T+1<lim;i++){
for(int j=1;j<=m;j++)if(g[i]*A[j]+1<1e18){
calcs(g[i]*A[j]+1);
lim=min(lim,T+sh);
if(T+2<lim) f[++fh]=g[i]*A[j]+1;
}
calcs(g[i]);
for(int j=1;j<=sh;j++) if(T+2<lim) f[++fh]=g[i]/st[j];
}
/*if(f.size()>30){
gdb(f.size());
cerr<<n<<' '<<m<<' ';
for(int k=1;k<=m;k++) cerr<<A[k]<<' ';cerr<<'\n';
} */
}
printf("%d\n",lim);
// if(clock()*1.0/CLOCKS_PER_SEC>11.7) exit(0);
}
// void init(){
// for(int i=2;i<=k;i++){
// if(!flag[i]) pr[++ph]=i,La[i]=i;
// for(int j=1;j<=ph&&i*pr[j]<=k;j++) {
// flag[i*pr[j]]=1;La[i*pr[j]]=pr[j];
// if(i%pr[j]==0) break;
// }
// }
// }
int main(){
int t=1;
// init();
scanf("%d",&t);
while(t--) Solve();
cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}