#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r
using namespace std;
const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 7;
const int maxn = 10 + 66;
long long n, a[maxn], r[maxn];
long long gcd (long long a, long long b)
{
if (b == 0)
return a;
return gcd (b, a % b);
}
long long gcd_ex (long long a, long long b, long long &x, long long &y)
{
if (b == 0) { x = 1; y = 0; return a; }
long long d = gcd_ex (b, a % b, y, x);
y = y - a / b * x;
return d;
}
long long mod_equ_set ()
{
long long M = a[0], R = r[0], x, y, d;
for (int i = 1; i < n; i++)
{
d = gcd_ex (M, a[i], x, y);
if ((r[i] - R) % d)
return -1;
x = (r[i] - R) / d * x % (a[i] / d);
R += x * M;
M = M / d * a[i];
R %= M;
}
return R > 0 ? R : R + M;
}
int main()
{
// ifstream cin ("aaa.txt");
int t;
cin >> t;
while (t--)
{
long long val, ans = 1;
cin >> val >> n;
for (int i = 0; i < n; i++)
{
cin >> a[i];
ans = ans / gcd (max (ans, a[i]), min (ans, a[i])) * a[i];
}
for (int i = 0; i < n; i++)
cin >> r[i];
long long x0 = mod_equ_set (), tot = 0;
if (x0 == -1)
{
cout << "0" << endl;
continue;
}
if (x0 <= val)
tot = 1 + (val - x0) / ans;
if (x0 == 0 && tot)
x0--;
cout << tot << endl;
}
return 0;
}