#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[200009];
LL dp[200009],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;
}
#define md ((l+r)>>1)
int rt[800009],kk;
struct o_t{
	int ls,rs;LL mi;
} sg[50000009];
inline int nw() {
	++kk;
	sg[kk].ls=sg[kk].rs=0;sg[kk].mi=0x3f3f3f3f3f3f3f3f;
	return kk;
}
void up2(int n,int l,int r,int p,LL v) {
	if(!rt[n]) rt[n]=nw();
	n=rt[n];
	while(l<r) {
		sg[n].mi=std::min(sg[n].mi,v);
		if(p<=md) {
			if(!sg[n].ls) sg[n].ls=nw();
			n=sg[n].ls;r=md;
		} else {
			if(!sg[n].rs) sg[n].rs=nw();
			n=sg[n].rs;l=md+1;			
		}
	}
	sg[n].mi=std::min(sg[n].mi,v);
}
LL qr2(int n,int l,int r,int p) {
	n=rt[n];
	LL as=0x3f3f3f3f3f3f3f3f;
	while(n&&l<r) {
		if(p<=md) {
			n=sg[n].ls;
			r=md;
		} else {
			as=std::min(as,sg[sg[n].ls].mi);
			n=sg[n].rs;
			l=md+1;
		}
	}
	return std::min(as,sg[n].mi);
}
#define ls (n<<1)
#define rs ((n<<1)|1)
void build(int n,int l,int r) {
	rt[n]=0;
	if(l==r) return;
	build(ls,l,md),build(rs,md+1,r);
}
void up(int n,int l,int r,int p,int p2,LL v) {
	up2(n,0,N,p2,v);
	if(l==r) return;
	if(p<=md) up(ls,l,md,p,p2,v);else up(rs,md+1,r,p,p2,v);
}
LL qr(int n,int l,int r,int L,int R,int p2) {
	if(r<L||R<l) return 0x3f3f3f3f3f3f3f3f;
	if(L<=l&&r<=R) {
		return qr2(n,0,N,p2);
	}
	return std::min(qr(ls,l,md,L,R,p2),qr(rs,md+1,r,L,R,p2));
}
signed main(void) {
	sg[0].mi=0x3f3f3f3f3f3f3f3f;
	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);
		tp[0]=(n_t){0,0,0};
		for(int i=0;i<=qq;i++) dp[i]=0x3f3f3f3f3f3f3f3f;
		LL ans=0x3f3f3f3f3f3f3f3f;
		dp[0]=0;
		build(1,0,qq);kk=0;
		up(1,0,qq,0,0,0);
		for(int i=1;i<=qq;i++) {
			int l=0,r=i-1,mm;
			while(l<r) {
				mm=(l+r+1)/2;
				if(tp[mm].r-tp[mm].l+1<=tp[i].va) l=mm;else r=mm-1;
			}
			dp[i]=qr(1,0,qq,0,l,tp[i].l-1);
//			for(int j=0;j<=l;j++)  {
//				if(tp[j].r<tp[i].l) {
//					dp[i]=std::min(dp[i],dp[j]);
//				}
//			}
			dp[i]+=C+1ll*tp[i].va*(s[tp[i].r]-s[tp[i].l-1]);
			ans=std::min(ans,dp[i]);
			up(1,0,qq,i,tp[i].r,dp[i]);
		}
		printf("%lld\n",ans);
	}
}