1 #include<bits/stdc++.h>

 2 using namespace std;

 3 typedef long long ll;

 4 ll t,n,m,a1,b1,a2,b2,c,k,ans;

 5 const int N=52;

 6 ll s[N],r[N];

 7 ll ex_gcd(ll a,ll b,ll &x,ll &y)

 8 {

 9     if(!b){x=1,y=0;return a;};

10     ll d=ex_gcd(b,a%b,x,y);

11     ll tmp=x;

12     x=y,y=tmp-a/b*y;

13     return d;

14 }

15 int main()

16 {

17     scanf("%lld",&t);

18     while(t--)

19     {

20         ll x,y,a,b;

21         bool flag=true;

22         scanf("%lld%lld",&n,&m);

23         for(int i=1;i<=m;i++) scanf("%lld",&s[i]);

24         for(int i=1;i<=m;i++) scanf("%lld",&r[i]);

25         a1=s[1],b1=r[1];

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

27         {

28             a2=s[i],b2=r[i];

29             a=a1,b=a2,c=b2-b1;

30             ll d=ex_gcd(a,b,x,y);

31             if(c%d!=0) {cout<<0<<'\n';flag=0;break;}

32             k=b/d;

33             x=(x*(c/d)%k+k)%k;

34             b1=a1*x+b1;

35             a1=a1*(a2/d);

36         }

37         if(flag)

38         {

39             if(n-b1<0) cout<<0<<'\n';

40             else

41             {

42                 ans=(n-b1)/a1+(b1!=0);

43                 cout<<ans<<'\n';

44             }

45         }

46     }

47     return 0;

48 }