#include <bits/stdc++.h>
#define LL long long
int T,N,C,qq,a[200009],b[200009],aa[44],bb[44],la[200009];
struct n_t{
	int l,r,va;
} tp[10000009];
LL dp[10000009],s[200009];
bool cmp(n_t x,n_t y) {
	if(x.r-x.l!=y.r-y.l) return x.r-x.l<y.r-y.l;
	return x.l<y.l;
}
signed main(void) {
	scanf("%d",&T);
	while(T--) {
		scanf("%d %d",&N,&C);
		int w=0;
		dp[0]=0;
		for(int i=1;i<=N;i++) {
			scanf("%d",&a[i]);
			dp[i]=0;
		}
		for(int i=1;i<=N;i++) {
			scanf("%d",&b[i]);
			s[i]=s[i-1]+b[i];
			la[i]=-1;
		}
		int qq=0,id=0;
		for(int i=1;i<=N;i++) {
			aa[++id]=i;
			bb[id]=0;
			for(int j=1;j<=id;j++) {
				bb[j]=std::__gcd(bb[j],a[i]);
			}
			for(int j=id;j>=2;j--) {
				if(bb[j]==bb[j-1]) {
					for(int k=j-1;k<id;k++) {
						aa[k]=aa[k+1];
						bb[k]=bb[k+1];
					}
					id--;
					j=id+1;
				}
			}
			for(int j=1;j<=id;j++) {
				if(bb[j]<=i-aa[j]+1) {
					if(la[aa[j]]!=bb[j]) {
						tp[++qq]=(n_t){aa[j],i,bb[j]};
						la[aa[j]]=bb[j];
					}
				}
				if(i-bb[j]+1<=aa[j]&&i-bb[j]+1>aa[j-1]) {
					tp[++qq]=(n_t){i-bb[j]+1,i,bb[j]};
					la[i-bb[j]+1]=bb[j];
				}
			}
/*			for(int j=i;j<=N;j++) {
				gg=std::__gcd(gg,a[j]);
				if(gg<=j-i+1) {
					if(la!=gg) {
						tp[++qq]=(n_t){i,j,gg};						
					}
					la=gg;
				}
			}*/
		}
		std::sort(tp+1,tp+qq+1,cmp);
		assert(qq<=200000);
	}
}