/*

同余方程组为 X = ri （mod ai）

在范围内求X的个数

先求出特解 X0；

求出 ai数组的LCM；

则有 Xi = X0+LCM 均能满足方程组，判断是否在范围内！！

*/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

typedef long long LL;

LL Ai[20],Ri[20];

void Exgcd(LL a,LL b,LL& d,LL& x,LL& y)

{

    if(b == 0) {d = a, x = 1, y = 0;}

    else {Exgcd(b,a%b,d,y,x); y -= x*(a/b);}

}

LL Solve(LL* ai,LL* ri,LL n)

{

    LL r1 = ri[1], a1 = ai[1];

    LL x, y;

    bool Jug = true;

    for(LL i = 2; i <= n; ++i)

    {

        LL d;

        LL a = a1, b = ai[i], c = ri[i] - r1;

        Exgcd(a,b,d,x,y);

        if(c % d) Jug = false;

        LL t = b / d;

        x = (x * (c / d)% t+ t)%t;

        r1 = a1 * x + r1;

        a1 = a1 * (ai[i]/d);

    }

    if(Jug) return r1;

    else return -1;

}

LL gcd(LL a,LL b) {return b ? gcd(b,a%b) : a;}

int main()

{

    LL N,M,T;

    cin >> T;

    while(T--)

    {

        cin >> N >> M;

        LL Lcm = 1;

        for(LL i = 1; i <= M; ++i)

        {

            cin >> Ai[i];

            Lcm = Lcm / gcd(Lcm,Ai[i]) * Ai[i];

        }

        for(LL i = 1; i <= M; ++i)

        {

            cin >> Ri[i];

        }

        LL tmp = Solve(Ai,Ri,M);

        //cout << Lcm << endl;

        if(tmp == -1) cout << "0\n";

        else

        {

            LL ans = 0;

            if(tmp <= N) ans = 1 + (N - tmp) / Lcm;

            if(tmp == 0 && ans > 0) ans --;

            cout << ans << endl;

        }

    }

}