#include<bits/stdc++.h>
using namespace std;
#define int long long
#define re register
#define il inline
#define pii pair<int,int>
#define x first
#define y second
#define gc getchar()
#define rd read()
#define debug() puts("------------")

namespace yzqwq{
    il int read(){
        int x=0,f=1;char ch=gc;
        while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=gc;}
        while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=gc;
        return x*f;
    }
    il int qmi(int a,int b,int p){
        int ans=1;
        while(b){
            if(b&1) ans=ans*a%p;
            a=a*a%p,b>>=1;
        }
        return ans;
    }
    il int gcd(int a,int b){
        if(!b) return a;
        return gcd(b,a%b);
    }
    il int lcm(int a,int b){
        return a/gcd(a,b)*b;
    }
    il void exgcd(int a,int b,int &x,int &y){
        if(!b) return x=1,y=0,void(0);
        exgcd(b,a%b,x,y);
        int t=x;
        x=y,y=t-a/b*x;
        return ;
    }
    il int F(int n,int a,int b,int c){
        //sum{|_ (ai+b)/c _| i:0~n}
        if(!n) return b/c;
        if(!a) return (n+1)*(b/c);
        if(a>=c||b>=c){
            int x=a/b,y=b/c;
            return n*(n+1)/2*x+(n+1)*y+F(n,a%c,b%c,c);
        }
        int m=(a*n+b)/c;
        return n*m+F(m-1,c,c-b+1,a);
    }
    struct lb{
        int d[64];
        il void print(){
            for(re int i=0;i<63;++i)
            if(d[i]) printf("%lld:%lld\n",i,d[i]);
            return ;
        }
        lb(){memset(d,0,sizeof(d));}
        il void operator +=(int x){
            for(re int i=62;i>=0;--i){
                if(!(x&(1ll<<i))) continue;
                if(d[i]) x^=d[i];
                else return d[i]=x,void(0);
            }
            return ;
        }
        int& operator [](int x){
            return d[x];
        }
        il void operator +=(lb &x){
            for(re int i=62;i>=0;--i)
            if(x[i]) *this+=x[i];
            return ;
        }
        il friend lb operator +(lb &x,lb &y){
            lb z=x;
            for(re int i=62;i>=0;--i)
            if(y[i]) z+=y[i];
            return z;
        }
        il int Max_calc(){
            int ans=0;
            for(re int i=62;i>=0;--i)
            if((ans^d[i])>ans) ans^=d[i];
            return ans;
        }
    };
	mt19937 rnd(time(0));
}
using namespace yzqwq;
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)

const int N=1e5+10,inf=1e18;
int n,C;
int a[N],b[N],s[N];
int __[N],Gcd[N][20];
struct Tree{
	int l,r,mi;
}tr[N<<2];
struct node{
	int i,j,delta,k;
};
struct node_{
	int j,k;
};
vector<node_> vec_[N];
vector<node> vec[N];

il void up(int u){
	tr[u].mi=min(tr[ls(u)].mi,tr[rs(u)].mi);
	return ;
}
il void build(int u,int l,int r){
	tr[u].l=l,tr[u].r=r,tr[u].mi=inf;
	if(l==r) return ;
	int mid=l+r>>1;
	build(ls(u),l,mid),build(rs(u),mid+1,r);
	return ;
}
il void modify(int u,int x,int y){
	if(tr[u].l==tr[u].r) return tr[u].mi=min(tr[u].mi,y),void(0);
	int mid=tr[u].l+tr[u].r>>1;
	if(x<=mid) modify(ls(u),x,y);
	else modify(rs(u),x,y);
	return up(u),void(0);
}
il int query(int u,int l,int r){
	if(tr[u].l>=l&&tr[u].r<=r) return tr[u].mi;
	int mid=tr[u].l+tr[u].r>>1;
	if(l<=mid&&mid< r) return min(query(ls(u),l,r),query(rs(u),l,r));
	if(l<=mid) return query(ls(u),l,r);
	return query(rs(u),l,r);
}
il int get_gcd(int l,int r){
	int k=__[r-l+1];
	return gcd(Gcd[l][k],Gcd[r-(1ll<<k)+1][k]);
}

il void solve(){
	n=rd,C=rd;
	for(re int i=0;i<=n;++i) __[i]=log2(i),vec[i].clear(),vec_[i].clear();
	for(re int i=1;i<=n;++i) a[i]=rd,Gcd[i][0]=a[i];
	for(re int i=1;i<=n;++i) b[i]=rd,s[i]=s[i-1]+b[i];
	for(re int j=1;j<20;++j)
	for(re int i=1;i+(1ll<<j)-1<=n;++i) Gcd[i][j]=gcd(Gcd[i][j-1],Gcd[i+(1ll<<(j-1))][j-1]);
	for(re int r=1;r<=n;++r){
		int u=r;
		while(u>=1){
			int gcdd=get_gcd(u,r);
			int le=1,ri=u,w=-1;
			while(le<=ri){
				int mid=le+ri>>1;
				if(get_gcd(mid,r)>=gcdd) w=mid,ri=mid-1;
				else le=mid+1;
			}
			int x=w,y=u;
			//r+1-gcdd>=l
			int l=r+1-gcdd;
			l=min(l,y);
			if(l<x){
				u=x-1;
				continue;
			}
			vec[l-1].push_back({r,r-l+1,gcdd*s[r]-gcdd*s[l-1]+C,gcdd});
			u=x-1;
		}
	}
	build(1,0,N-1);
	vec_[0].push_back({0,0});
	for(re int r=0;r<=n;++r){
		for(auto x:vec_[r]){
			int j=x.j,k=x.k;
			modify(1,x.j,x.k);
		}
		for(auto x:vec[r]){
			int i=x.i,j=x.j,delta=x.delta,k=x.k;
			int Min=query(1,0,k);
			vec_[i].push_back({j,delta+Min});
		}
	}
//	if(tr[1].mi==0) assert(0);
	printf("%lld\n",query(1,1,N-1));
    return ;
}

signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
    int t=rd;while(t--)
    solve();
    return 0;
}