#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define ll long long
#define PII pair<int,int>
#define endl '\n'
#define lson 2*p
#define rson 2*p+1
const int N=1e5+10;
const int mod=1e9+7;
int f[N][20];
int a[N];
int n,c,tot;
ll w[N*17*18],sum[N];
int rt[N];
int ls[N*17*18],rs[N*17*18];
int lg[N],pw[N];
int gcd(int a,int b) {return (b?gcd(b,a%b):a);}
void init() {
	for(int i=1;i<=n;i++) f[i][0]=a[i];
	for(int j=1;j<=18;j++) {
		for(int i=1;i+pw[j]-1<=n;i++) {
			f[i][j]=gcd(f[i][j-1],f[i+(pw[j-1])][j-1]);
		}
	}
}
int query(int l,int r) {
	int k=lg[r-l+1];
	return gcd(f[l][k],f[r-pw[k]+1][k]);
}
void pushup(int now) {
	w[now]=min(w[ls[now]],w[rs[now]]);
}
int build(int l,int r)
{
	int u=++tot; w[tot]=1e18;
	if(l<r)
	{
		int mid=((l+r)>>1);
		ls[u]=build(l,mid),rs[u]=build(mid+1,r);
	}
	return u;
}
int modify(int now,int l,int r,int pos,ll x) {
	int v=++tot;
	w[v]=min(w[now],x);
	ls[v]=ls[now],rs[v]=rs[now];
	if(l<r) {
		int mid=l+r>>1;
		if(pos<=mid) ls[v]=modify(ls[v],l,mid,pos,x);
		else rs[v]=modify(rs[v],mid+1,r,pos,x);
	}
	return v;
}
ll query(int now,int l,int r,int ql,int qr) {
	if(l>=ql&&r<=qr) return w[now];
	ll ans=1e18;
	int mid=l+r>>1;
	if(ql<=mid) ans=min(ans,query(ls[now],l,mid,ql,qr));
	if(qr>mid) ans=min(ans,query(rs[now],mid+1,r,ql,qr));
	return ans;
}
void solve() {
	cin>>n>>c;
	for(int i=1;i<=n;i++) cin>>a[i],rt[i]=0;
	tot=0;
	build(0,n);
	rt[0]=0;
	rt[0]=modify(0,0,n,0,0);
	for(int i=1;i<=n;i++) {
		int x;
		cin>>x;
		sum[i]=sum[i-1]+x;
	}
	init();
	for(int i=1;i<=n;i++) {
		int len=1;
		rt[i]=rt[i-1];
		while(len<=i) {
			int g=query(i-len+1,i);
			int res=len,l=1,r=i;
			while(l<=r) {
				int mid=l+r>>1;
				if(query(i-mid+1,i)==g) res=mid,l=mid+1;
				else r=mid-1;
			}
			if(g<=res) {
				int j=max(g,len);
				ll val=query(rt[i-j],0,n,0,g)+g*(sum[i]-sum[i-j])+c;
				rt[i]=modify(rt[i],0,n,j,val);
			}
			len=res+1;
		}
	}
	cout<<query(rt[n],0,n,1,n)<<"\n";
}
signed main() {
    int T=1;
    ios::sync_with_stdio(false);
    cin.tie(0);
	cout.tie(0);
	lg[0]=-1;
	for(int i=1;i<=1e5;i++) lg[i]=lg[i/2]+1;
	pw[0]=1;
	for(int i=1;i<=20;i++) pw[i]=pw[i-1]*2;
    cin>>T;
    while(T--) {    
        solve();
    }
}