/*
同余方程组为 X = ri （mod ai）
在范围内求X的个数
先求出特解 X0；
求出 ai数组的LCM；
则有 Xi = X0+LCM 均能满足方程组，判断是否在范围内！！
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long LL;
LL Ai[20],Ri[20];
void Exgcd(LL a,LL b,LL& d,LL& x,LL& y)
{
if(b == 0) {d = a, x = 1, y = 0;}
else {Exgcd(b,a%b,d,y,x); y -= x*(a/b);}
}
LL Solve(LL* ai,LL* ri,LL n)
{
LL r1 = ri[1], a1 = ai[1];
LL x, y;
bool Jug = true;
for(LL i = 2; i <= n; ++i)
{
LL d;
LL a = a1, b = ai[i], c = ri[i] - r1;
Exgcd(a,b,d,x,y);
if(c % d) Jug = false;
LL t = b / d;
x = (x * (c / d)% t+ t)%t;
r1 = a1 * x + r1;
a1 = a1 * (ai[i]/d);
}
if(Jug) return r1;
else return -1;
}
LL gcd(LL a,LL b) {return b ? gcd(b,a%b) : a;}
int main()
{
LL N,M,T;
cin >> T;
while(T--)
{
cin >> N >> M;
LL Lcm = 1;
for(LL i = 1; i <= M; ++i)
{
cin >> Ai[i];
Lcm = Lcm / gcd(Lcm,Ai[i]) * Ai[i];
}
for(LL i = 1; i <= M; ++i)
{
cin >> Ri[i];
}
LL tmp = Solve(Ai,Ri,M);
//cout << Lcm << endl;
if(tmp == -1) cout << "0\n";
else
{
LL ans = 0;
if(tmp <= N) ans = 1 + (N - tmp) / Lcm;
if(tmp == 0 && ans > 0) ans --;
cout << ans << endl;
}
}
}