#include <iostream>

#include <cstdio>

#define ll long long

using namespace std;

ll c[],m[],n,t,tot;

void exgcd(ll A,ll B,ll& d,ll& x,ll& y)

{

    if (B==) { x=,y=,d=A; }

    else { exgcd(B,A%B,d,y,x); y-=A/B*x; }

}

ll china()

{

    bool ans=true;

    ll am=m[],d,y0,z0;

    ll ac=c[];

        for (ll i=; i<=n; i++)

        {

            exgcd(am,m[i],d,y0,z0);

            if ((ac-c[i])%d!=)

            {

                ans=false;

                break;

            }

            y0=(c[i]-ac)/d*y0;

            y0=((y0%(m[i]/d))+(m[i]/d))%(m[i]/d);

            ac=am*y0+ac,am=am/d*m[i],ac=(ac%am+am)%am;

        }

        if (ac==) ac=am;//这里是题目说明了整数，不能为0哦。

    if (ac>tot || ans==false) return ;

    return (tot-ac)/am+;

}

int main()

{

    cin>>t;

    while (t--)

    {

        cin>>tot>>n;

        for (ll i=; i<=n; i++) scanf("%I64d",&m[i]);

        for (ll i=; i<=n; i++) scanf("%I64d",&c[i]);

        cout<<china()<<endl;

    }

    return ;

}