#include <iostream>

#include <stdio.h>

#include<string.h>

#include<algorithm>

#include<string>

#include<ctype.h>

using namespace std;

#define MAXN 10000

int a[];

int b[];

int n,m;

int gcd(int a,int b)

{

    return b?gcd(b,a%b):a;

}

int lcm(int a,int b)

{

    return a*b/(gcd(a,b));

}

int exgcd(int a,int b,int &x,int &y)

{

    if(!b)

    {

        x=;

        y=;

        return a;

    }

    int tt=exgcd(b,a%b,x,y);

    int t;

    t=x;

    x=y;

    y=(t-a/b*y);

    return tt;

}

int solve()

{

    int a1,a2,b1,b2,x,y,A,B,C,d,t;

    a1=a[];

    b1=b[];

    for(int i=;i<m;i++)

    {

        a2=a[i];

        b2=b[i];

        A=a1;

        B=a2;

        C=b2-b1;

        d=exgcd(A,B,x,y);

        if(C%d)

        {

            return -;

        }

        t=B/d;

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

        b1=a1*x+b1;

        a1=a1/d*a2;

    }

    return b1;

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d%d",&n,&m);

        for(int i=;i<m;i++)

        {

            scanf("%d",a+i);

        }

        for(int i=;i<m;i++)

        {

            scanf("%d",b+i);

        }

        int lm=;

        for(int i=;i<m;i++)

        {

            lm=lcm(a[i],lm);

        }

        int ans=;

        int tmp=solve();

        if(tmp==-)

        {

            puts("");

            continue;

        }

        if(tmp<=n)

            ans+=+(n-tmp)/lm;

        if(ans&&tmp==)

            ans--;

        cout<<ans<<endl;

    }

    return ;

}