#include <iostream>#include <stdio.h>#include<string.h>#include<algorithm>#include<string>#include<ctype.h>using namespace std;#define MAXN 10000int a[11];int b[11];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=1;        y=0;        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[0];    b1=b[0];    for(int i=1;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 -1;        }        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=0;i<m;i++)        {            scanf("%d",a+i);        }        for(int i=0;i<m;i++)        {            scanf("%d",b+i);        }        int lm=1;        for(int i=0;i<m;i++)        {            lm=lcm(a[i],lm);        }        int ans=0;        int tmp=solve();        if(tmp==-1)        {            puts("0");            continue;        }        if(tmp<=n)            ans+=1+(n-tmp)/lm;        if(ans&&tmp==0)            ans--;        cout<<ans<<endl;    }    return 0;}