#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <algorithm>using namespace std;#define inf (0x3f3f3f3f)typedef long long int LL;#include <iostream>#include <sstream>#include <vector>#include <set>#include <map>#include <queue>#include <string>const int maxn = 500 + 20;LL mod[maxn];LL r[maxn];LL gcd(LL n, LL m) {    if (n % m == 0) return m;    else return gcd(m, n % m);}LL lcm(LL n, LL m) {    return n / gcd(n, m) * m;}LL exgcd (LL a,LL mod,LL &x,LL &y) {    //求解a关于mod的逆元     ★：当且仅当a和mod互质才有用    if (mod==0) {        x=1;        y=0;        return a;//保留基本功能，返回最大公约数    }    LL g=exgcd(mod,a%mod,x,y);    LL t=x;    //这里根据mod==0  return回来后，    x=y;    //x,y是最新的值x2,y2,改变一下，这样赋值就是为了x1=y2    y=t-(a/mod)*y;    // y1=x2(变成了t)-[a/mod]y2;    return g;            //保留基本功能，返回最大公约数}bool get_min_number (LL a,LL b,LL c,LL &x,LL &y) {  //得到a*x+b*y=c的最小整数解    LL abGCD = gcd(a,b);    if (c % abGCD != 0) return false;//不能整除GCD的话，此方程无解    a /= abGCD;    b /= abGCD;    c /= abGCD;    LL tx,ty;    exgcd(a,b,tx,ty); //先得到a*x+b*y=1的解，注意这个时候gcd(a,b)=1    x = tx * c;    y = ty * c; //同时乘上c，c是约简了的。得到了一组a*x + b*y = c的解。    LL haveSignB = b;    if (b < 0) b = -b;   //避免mod负数啊，模负数没问题，模了负数后+负数就GG    x = (x % b + b) % b; //最小解//    if (x == 0) x = b; //避免x = 0不是"正"整数  不要用这个，溢出    y = (c - a * x) / haveSignB;    return true;//true代表可以}void work () {    LL n, m;    cin >> n >> m;    for (int i = 1; i <= m; ++i) {        cin >> mod[i];    }    for (int i = 1; i <= m; ++i) {        cin >> r[i];    }    LL mm = mod[1];    LL ansx = 0;    LL rr = r[1];    for (int i = 2; i <= m; ++i) {        LL x, y;        bool ret = get_min_number(mm, -mod[i], r[i] - rr, x, y);        if (ret == false) {            printf("0\n");            return;        }        ansx = mm * x + rr;        mm = lcm(mm, mod[i]);        rr = ansx % mm;    }    int add = rr != 0;    if (rr > n) {        printf("0\n");        return ;    }    cout << (n - rr) / mm + add << endl;    return ;}int main() {#ifdef local    freopen("data.txt","r",stdin);#endif    int t;    cin >> t;    while (t--) work();    return 0;}