#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int MaxM=11;int a[MaxM],b[MaxM];void exgcd(int a,int b,int &d,int &x,int &y){	if(b==0){		x=1; y=0;		d=a;	}	else{		exgcd(b,a%b,d,x,y);		int tmp=x;		x=y;		y=tmp-(a/b)*y;	}}int gcd(int a,int b){	if(b==0) return a;	return gcd(b,a%b);}int main(){	int t; int a1,r1,a2,r2; int aa,bb,cc,dd; int x,y; int g;	scanf("%d",&t);	int n,m;	bool ifhave;	while(t--){		scanf("%d%d",&n,&m);		g=1;		for(int i=0;i<m;i++){			scanf("%d",&a[i]);			if(i==0){ g=a[i]; continue; }			g=g*a[i]/gcd(g,a[i]);		}		for(int i=0;i<m;i++)		scanf("%d",&b[i]);		a1=a[0]; r1=b[0];		ifhave=true;		for(int i=1;i<m;i++){			a2=a[i]; r2=b[i];			aa=a1; bb=a2; cc=r2-r1;			exgcd(aa,bb,dd,x,y);			if(cc%dd!=0){				ifhave=false;				break;			}			int t=bb/dd;			x=(x*(cc/dd)%t+t)%t;			r1=a1*x+r1;			a1=a1*(a2/dd);		}		if(!ifhave)		printf("0\n");		else{			int tmp=r1;			int i;			for(i=1;;i++){				if(tmp+(i-1)*g>n) break;			}			if(tmp==0) i--;			printf("%d\n",i-1);		}	}	return 0;}