#include<bits/stdc++.h>
#define int long long
using namespace std;

int dp[1005][1005],pres[1005][1005];
int T,n,C,b[100005],ans;
signed flog[100005],a[100005],rmq[100005][17];
signed rot[100005],ls[40000005],rs[40000005],pt1;
int mnm[40000005];

char kudu;

int read(){
	int x=0,ch=1;for(;!isdigit(kudu);kudu=getchar())if(kudu=='-')ch=-1;
	for(;isdigit(kudu);kudu=getchar())x=x*10+(kudu^48);
	return x*ch;
}

int ql,qr,qv;

inline int gcd(int x,int y){
	while(y){int r=y;y=x%y;x=r;}
	return x;
}

inline int nmsl(int l,int r){
	int c=flog[r-l+1];return gcd(rmq[l][c],rmq[r-(1<<c)+1][c]);
}

inline int build(int l,int r){
	int x=++pt1;mnm[x]=0x3f3f3f3f3f3f3f3f;if(l==r)return x;
	int md=(l+r>>1);ls[x]=build(l,md);rs[x]=build(md+1,r);return x;
}

int add(int ox,int l,int r){
	int x=++pt1;mnm[x]=min(mnm[ox],qv);if(l==r)return x;
	int md=(l+r>>1);
	ls[x]=(ql<=md?add(ls[ox],l,md):ls[ox]);
	rs[x]=(ql>md?add(rs[ox],md+1,r):rs[ox]);
	return x;
}

void query(int x,int l,int r){
	if(ql>r||qr<l)return;if(ql<=l&&qr>=r){qv=min(qv,mnm[x]);return;}
	int md=(l+r>>1);query(ls[x],l,md);query(rs[x],md+1,r);
}

signed main(){
	for(int i=2;i<=100000;i++)flog[i]=flog[i>>1]+1;
	cin.tie(0)->sync_with_stdio(0);
	T=read();
	while(T--){
		n=read();C=read();
		for(int i=1;i<=n;i++){
			a[i]=read();rmq[i][0]=a[i];
		}
		for(int i=1;i<=n;i++){
			b[i]=read();b[i]+=b[i-1];
		}
		if(n<=10){
			ans=0x3f3f3f3f3f3f3f3f;
			for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)dp[i][j]=0x3f3f3f3f3f3f3f3f;
			for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)pres[i][j]=0x3f3f3f3f3f3f3f3f;
			dp[0][0]=0;for(int j=0;j<=n;j++)pres[0][j]=0;
			for(int i=1;i<=n;i++){
				for(int j=0;j<=n;j++)dp[i][j]=dp[i-1][j];
				for(int j=i,g=0;j>=1;j--){
					g=gcd(g,a[j]);
					if(g<=i-j+1)dp[i][i-j+1]=min(dp[i][i-j+1],pres[j-1][g]+g*(b[i]-b[j-1])+C);
				}
				pres[i][0]=dp[i][0];for(int j=1;j<=n;j++)pres[i][j]=min(pres[i][j-1],dp[i][j]);
			}
			for(int j=1;j<=n;j++)ans=min(ans,dp[n][j]);
			cout<<ans<<'\n';continue;
		}
		for(int o=1;o<17;o++){
			for(int i=1;i<=n-(1<<o)+1;i++)rmq[i][o]=gcd(rmq[i][o-1],rmq[i+(1<<o-1)][o-1]);
		}
		rot[0]=build(0,100000);
		ql=qv=0;rot[0]=add(rot[0],0,100000);
		for(int i=1;i<=n;i++){
			rot[i]=rot[i-1];
			for(int j=i,g=a[i],nmzl=0x3f3f3f3f3f3f3f3f;;){
				int lj=i;
				for(int o=16;o>=0;o--){
					if(lj>=(1<<o)&&rmq[lj-(1<<o)+1][o]%g==0)lj-=(1<<o);
				}
				if(g<=i-j+1){
					ql=0;qr=g;qv=0x3f3f3f3f3f3f3f3f;query(rot[j-1],0,100000);
					ql=i-j+1;qv+=C+g*(b[i]-b[j-1]);
					if(qv<nmzl){nmzl=qv;rot[i]=add(rot[i],0,100000);}
				}
				else if(g<=i-lj){
					ql=0;qr=g;qv=0x3f3f3f3f3f3f3f3f;query(rot[i-g],0,100000);
					ql=g;qv+=C+g*(b[i]-b[i-g]);
					if(qv<nmzl){nmzl=qv;rot[i]=add(rot[i],0,100000);}
				}
				if(lj){
					g=nmsl(lj,i);j=lj;
				}
				else break;
			}
		}
		ql=1;qr=100000;qv=0x3f3f3f3f3f3f3f3f;query(rot[n],0,100000);cout<<qv<<'\n';
		for(int i=1;i<=pt1;i++)ls[i]=rs[i]=0;pt1=0;
	}
	return 0;
}