#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 rt[N],ls[N*17*18],rs[N*17*18];
ll w[N*17*18],sum[N];
int a[N],tot;
int f[N][19],pw[N],n,C,lg[N];
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]);
}
int build(int l,int r) {
	tot++;
	int root=tot;
	if(l==r) {
		if(!l) w[root]=0;
		else w[root]=1e18;
		return tot;
	}
	int mid=l+r>>1;
	ls[root]=build(l,mid);
	rs[root]=build(mid+1,r);
	w[root]=min(w[ls[root]],w[rs[root]]);
	return root;
}
int update(int root,int l,int r,int pos,ll k) {
	int res=++tot;
	ls[res]=ls[root],rs[res]=rs[root];
	w[res]=min(w[root],k);
	if(l==r) {
		w[res]=min(w[res],k);
		return res;
	}
	int mid=l+r>>1;
	if(pos<=mid) ls[res]=update(ls[root],l,mid,pos,k);
	else rs[res]=update(rs[root],mid+1,r,pos,k);
	
	return res;
}
ll query(int root,int l,int r,int ql,int qr) {
	if(l>=ql&&r<=qr) return w[root];
	ll ans=1e18;
	int mid=l+r>>1;
	if(ql<=mid) ans=min(ans,query(ls[root],l,mid,ql,qr));
	if(qr>mid) ans=min(ans,query(rs[root],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;
	for(int i=1,x;i<=n;i++) cin>>x,sum[i]=sum[i-1]+x;
	init();
	tot=0;
	rt[0]=build(0,n);
	for(int i=1;i<=n;i++) {
		int cur=i;
		rt[i]=rt[i-1];
		while(cur) {
			int res=0,l=1,r=cur;
			int now=query(cur,i);
			while(l<=r) {
				int mid=l+r>>1;
				if(query(mid,i)==now) res=mid,r=mid-1;
				else l=mid+1;
			}
			if(!res) res=1;
			int len=i-res+1;
			if(len>=now) {
				int j=min(i-now+1,cur);
				j=i-j+1;
				ll val=query(rt[i-j],0,n,0,now)+now*(sum[i]-sum[i-j])+C;
				rt[i]=update(rt[i],0,n,j,val);
			}
			cur=res-1;
		}
	}
	cout<<query(rt[n],0,n,1,n)<<endl;
}
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();
    }
}