3
10 3
1 2 3
0 1 2
100 7
3 4 5 6 7 8 9
1 2 3 4 5 6 7
10000 10
1 2 3 4 5 6 7 8 9 10
0 1 2 3 4 5 6 7 8 9

1
0
3

#include<stdio.h>
int a1,b1;
int a[11],b[11];
void EXGCD(int a,int b,int &x,int &y,int &c){
	if(!b){
		x=1;
		y=0;
		c=a;
		return ;
	}
	EXGCD(b,a%b,x,y,c);
	int temp=x;
	
	x=y;
	y=temp-a/b*y;
}
int China_2(int M[],int B[],int n){
	int i,ok=0,d,x,y,c;
	a1=M[0],b1=B[0];
	for(i=1;i<n;++i){
		if(ok) continue;
		EXGCD(a1,M[i],x,y,c);
		d=B[i]-b1;
		if(d%c){
			ok=1;
			continue;
		}
		int q=M[i]/c;
		x=(x*d/c%q+q)%q;
		b1=a1*x+b1;
		a1=a1*M[i]/c;
	}
	if(ok) return -1;
	else return b1?b1:b1+a1;
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int N,M,i; 
		scanf("%d%d",&N,&M);
		for(i=0;i<M;++i){
			scanf("%d",&a[i]);
		}
		for(i=0;i<M;++i){
			scanf("%d",&b[i]);
		}
		int t=China_2(a,b,M);
		if(t==-1||t>N) printf("0\n");
		else{
			//printf("%d#\n",t);
			printf("%d\n",(N-t)/a1+1);
		}
	}
	return 0;
}