#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define int ll

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using pii = pair<int, int>;
using vi = vector<int>;
#define fi first
#define se second
#define pb push_back

const int N = 1e8;
int maxp[N];
vector<int> primes;

vector<int> rozklad(int n)
{
    if (n == 1) return {};
    if (n < N)
    {
        vector<int> res;
        int last = -1;
        while (n > 1)
        {
            if (maxp[n] != last)
                res.pb(maxp[n]), last = maxp[n];
            n/=maxp[n];
        }
        return res;
    }

    vector<int> res;
    for (int i : primes)
    {
        if (i*i > n)
            break;
        if (n % i == 0)
        {
            if (n%i==0)
            {
                n/=i;
                res.pb(i);
                while (n%i==0)
                    n/=i;
            }
            if (n < N)
            {
                auto small = rozklad(n);
                reverse(res.begin(), res.end());
                for (int i : res)
                    small.pb(i);
                return small;
            }
        }
    }
    if (n >= N*N)
    {
//        cout<<n<<" ? "<<endl;
        for (int i=N; i*i<=N; i++)
            if (n%i==0)
            {
                n/=i;
                res.pb(i);
                while (n%i == 0)
                    n/=i;
            }
    }
    res.pb(n);
    reverse(res.begin(), res.end());
    return res;
}

int ans(int n, int m, int k)
{
    if (n == 1)
        return 0;
    if (k <= 0)
        return 100;

    int n0 = n;
    vector<int> p = rozklad(n);

    int A = p.size();
    int B = ans(n0*m+1, m, min<int>(k-1, A-2));
    B++;

    return min(A, B);
}

int real(int n, int m, int k)
{
    if (n == 1)
        return 0;
    if (k <= 0)
        return 100;

    int n0 = n;
    vector<int> p = rozklad(n);
    int A = p.size();
    A = min(A, real(n0*m+1, m, min(A, k-1)-2)+1);
    reverse(p.begin(), p.end());
    for (int i : p)
        A = min(A, real(n0/i, m, min(A-2, k-1))+1);
    return A;
}

vector<pair<int, int> > seven =
{
    {7, 1515625},
    {23, 959769},
    {23, 1560789},
    {29, 632043},
    {41, 1328967},
    {43, 1328125},
};
map<pair<int, int>, int> mp =
{
    {{966249, 1}, 6},
{{1156375, 1}, 6},
{{1189375, 1}, 6},
{{1191375, 1}, 6},
{{1203903, 1}, 6},
{{1275831, 1}, 6},
{{1299920, 1}, 6},
{{1299968, 1}, 6},
};

int m;
int M[10];

int binpow(int a, int b, int m)
{
    int r=1;
    while (b>0)
    {
        if (b%2)
            r=r*a%m;
        a=a*a%m;
        b/=2;
    }
    return r;
}
mt19937_64 rng;
bool isprime(int n)
{
    if (n<N)
        return (maxp[n]==n);
    if (n%2==0 || n%3==0 || n%5==0)
        return false;

    int p=n-1;
    int c=0;
    while (p%2==0)
        c++, p/=2;
    for (int _=0; _<20; _++)
    {
        int a = rng()%(n-1)+1;
        int pw = binpow(a, p, n);
        if (pw != 1 && pw != n-1)
        {
            bool ok = false;
            for (int i=1; i<c; i++)
            {
                pw = pw*pw%n;
                if (pw == n-1)
                {
                    ok = true;
                    break;
                }
            }
            if (!ok)
                return false;
        }
    }
    return true;

//    if (n < N)
//        return maxp[n] == n;
//    for (int i : primes)
//    {
//        if (i*i > n)
//            return true;
//        if (n%i == 0)
//            return false;
//    }
//    exit(1);
}

const int MX = 6;
int solve(int n)
{
    if (m == 1)
        for (auto [mx, nx] : seven)
            if (M[0] == mx && n == nx)
                return 7;

    int steps = 0;
    vector<int> cur = {n};
    while (true)
    {
        for (int i : cur)
            if (isprime(i))
                return steps+1;
        if (steps == MX-3)
        {
            for (int i : cur)
            {
                if (i < N)
                    if (maxp[i/maxp[i]] == i/maxp[i])
                        return steps+2;
                if (i >= N)
                {
                    for (int j : primes)
                    {
                        if (j*j > i)
                            break;
                        if (i%j==0)
                        {
                            if (isprime(i/j))
                                return steps+2;
                            else
                                break;
                        }
                    }
                }
                for (int j=0; j<m; j++)
                    if (isprime(i*M[j]+1))
                        return steps+2;
            }
            break;
        }
        if (steps == MX-2)
            break;

        vector<int> nt;
        for (int i : cur)
        {
            for (int j=0; j<m; j++)
                nt.pb(i*M[j]+1);
            for (int j : rozklad(i))
                nt.pb(i/j);
        }
        cur = nt;
        steps++;
    }
    return MX;
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    for (int i=2; i<N; i++)
        if (maxp[i] == 0)
        {
            primes.pb(i);
            for (int j=i; j<N; j+=i)
                maxp[j] = i;
        }
    int q;
    cin>>q;
    while (q--)
    {
        int n;
        n = 1553375;
        m = 1;
        M[0] = 1;
        cin>>n>>m;
        for (int i=0; i<m; i++)
            cin>>M[i];

//        if (clock()*1.0/CLOCKS_PER_SEC > 10)
//        {
//            cout<<q<<"\n";
//            return 0;
//        }
//        if (q < 10)
            cout<<solve(n)<<"\n";
//        int x = solve(n);
//        m^=x;
    }
    return 0;

    ofstream fout("collatz.txt");
    int crit = 6;
    int cnt = 0;
    for (int m=1; m<=64; m++)
    {
        cout<<"// "<<m<<" : ";
        for (int i=1; i<=2000000; i++)
        {
            int c = ans(i, m, 8);
            if (c >= crit)
            {
                int x = real(i, m, c-1);
                if (x >= crit)
                    fout<<"{{"<<i<<", "<<m<<"}, "<<x<<"},\n", cnt++;
            }
        }
        cout<<cnt<<endl;
    }
}

/*
1 :
2 :
3 :
4 :
5 :
6 :
7 :
7 1515625 7
8 :
9 :
10 :
11 :
12 :
13 :
14 :
15 :
16 :
17 :
18 :
19 :
20 :
21 :
22 :
23 :
7 959769 7
7 1560789 7
24 :
25 :
26 :
27 :
28 :
29 :
7 632043 7
30 :
31 :
32 :
33 :
34 :
35 :
36 :
37 :
38 :
39 :
40 :
41 :
7 1328967 7
42 :
43 :
7 1328125 7
44 :
45 :
46 :
47 :
48 :
49 :
50 :
51 :
52 :
53 :

*******

{7, 1515625},
{23, 959769},
{23, 1560789},
{29, 632043},
{41, 1328967},
{43, 1328125},
*/