#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <math.h>
using namespace std;
typedef long long LL;
const int N = 10;
LL extend_gcd(LL a,LL b,LL &x,LL &y)
{
    if(b==0)
    {
        x=1,y=0;
        return a;
    }
    else
    {
        LL x1,y1;
        LL d = extend_gcd(b,a%b,x1,y1);
        x = y1;
        y = x1-a/b*y1;
        return d;
    }
}
LL m[N],a[N];///模数为m,余数为a, X % m = a
bool solve(LL &m0,LL &a0,LL m,LL a)
{
    long long y,x;
    LL g = extend_gcd(m0,m,x,y);
    LL t = a-a0>0?a-a0:a0-a;
    if( t%g )return false;
    x *= (a - a0)/g;
    x %= m/g;
    a0 = (x*m0 + a0);
    m0 *= m/g;
    a0 %= m0;
    if( a0 < 0 )a0 += m0;
    return true;
}
/**
* 无解返回false,有解返回true;
* 解的形式最后为 a0 + m0 * t (0<=a0<m0)
*/
bool MLES(LL &m0 ,LL &a0,LL n)///解为 X = a0 + m0 * k
{
    bool flag = true;
    m0 = 1;
    a0 = 0;
    for(int i = 0; i < n; i++)
        if( !solve(m0,a0,m[i],a[i]) )
        {
            flag = false;
            break;
        }
    return flag;
}
int main()
{
    int n;
    LL N;
    int tcase;
    scanf("%d",&tcase);
    while(tcase--)
    {
        scanf("%lld%d",&N,&n);
        for(int i=0; i<n; i++)
        {
            scanf("%lld",&m[i]);
        }
        for(int i=0; i<n; i++)
        {
            scanf("%lld",&a[i]);
        }
        LL m0,a0;
        bool flag = MLES(m0,a0,n);
        LL x = (a0%m0+m0)%m0;
        if(!flag) printf("0\n");
        else
        {
            if(x>N) printf("0\n");
            else{
                LL ans = (N-x)/m0;
                if(x==0) printf("%lld\n",ans);
                else printf("%lld\n",ans+1);
            }
        }
    }
    return 0;
}