#include <bits/stdc++.h>
#define LL long long
int T,N,C,qq,a[200009],b[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];
		}
		int qq=0;
		for(int i=1;i<=N;i++) {
			int l=i,gg=0,la=-1;
			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;
		for(int i=0;i<=qq;i++) {
			if(i) ans=std::min(ans,dp[i]);
			for(int j=i+1;j<=qq;j++)  {
				if(tp[i].r<tp[j].l&&tp[j].va>=tp[i].r-tp[i].l+1) {
					dp[j]=std::min(dp[j],dp[i]+1ll*tp[j].va*(s[tp[j].r]-s[tp[j].l-1])+C);
				}
			}
		}
		printf("%lld\n",ans);
	}
}