#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(auto i=(a);i<=(b);i++)
#define REP(i,a,b) for(auto i=(a);i>=(b);i--)
#define FORK(i,a,b,k) for(auto i=(a);i<=(b);i+=(k))
#define REPK(i,a,b,k) for(auto i=(a);i>=(b);i-=(k))
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
template<class T>
void ckmx(T& a,T b){
    a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
template<class T>
T gcd(T a,T b){
    return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
    return a/gcd(a,b)*b;
}
#define gc getchar()
#define eb emplace_back
#define pc putchar
#define ep empty()
#define fi first
#define se second
#define pln pc('\n');
#define islower(ch) (ch>='a'&&ch<='z')
#define isupper(ch) (ch>='A'&&ch<='Z')
#define isalpha(ch) (islower(ch)||isupper(ch))
template<class T>
void wrint(T x){
    if(x<0){
        x=-x;
        pc('-');
    }
    if(x>=10){
        wrint(x/10);
    }
    pc(x%10^48);
}
template<class T>
void wrintln(T x){
    wrint(x);
    pln
}
template<class T>
void read(T& x){
    x=0;
    int f=1;
    char ch=gc;
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=gc;
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=gc;
    }
    x*=f;
}
/*
主席树维护 i 结尾，最后一个区间长度 =j 的最小代价
ST 表维护区间 gcd
*/
const int maxn=1e5+5;
int n;
ll C;
int a[maxn];
ll b[maxn];
ll preb[maxn];
ll wb(int l,int r){
    return preb[r]-preb[l-1];
}
struct ST{
    int _gcd[18][maxn];
    void init(){
        FOR(i,1,n){
            _gcd[0][i]=a[i];
        }
        FOR(i,1,17){
            FOR(j,1,n-(1<<i)+1){
                _gcd[i][j]=gcd(_gcd[i-1][j],_gcd[i-1][j+(1<<i-1)]);
            }
        }
    }
    int qgcd(int l,int r){
        int _=__lg(r-l+1);
        return gcd(_gcd[_][l],_gcd[_][r-(1<<_)+1]);
    }
}st;
struct HJT{
    struct Node{
        int ls,rs;
        ll mn;
    }nd[32400005];
    // 1e5*(18^2)
    int ndcnt;
    void pushup(Node& x){
        x.mn=min(nd[x.ls].mn,nd[x.rs].mn);
    }
    void bd(int& rt,int l,int r){
        if(!rt)rt=++ndcnt;
        nd[rt].mn=1e18;
        if(l==r){
            return;
        }
        int mid=(l+r>>1);
        bd(nd[rt].ls,l,mid);
        bd(nd[rt].rs,mid+1,r);
    }
    void chg(int& rtold,int& rtnew,int l,int r,int x,ll _v){
        if(!rtnew){
            rtnew=++ndcnt;
            nd[rtnew].mn=nd[rtold].mn;
        }
        if(l==r){
            ckmn(nd[rtnew].mn,_v);
            return;
        }
        int mid=(l+r>>1);
        if(mid>=x){
            if(nd[rtnew].ls==nd[rtold].ls)nd[rtnew].ls=0;// 这个节点需要新建
            chg(nd[rtold].ls,nd[rtnew].ls,l,mid,x,_v);
        }
        else{
            if(nd[rtnew].rs==nd[rtold].rs)nd[rtnew].rs=0;// 同理
            chg(nd[rtold].rs,nd[rtnew].rs,mid+1,r,x,_v);
        }
        if(!nd[rtnew].ls)nd[rtnew].ls=nd[rtold].ls;
        if(!nd[rtnew].rs)nd[rtnew].rs=nd[rtold].rs;
        pushup(nd[rtnew]);
    }
    ll qmn(int rt,int curl,int curr,int l,int r){
        if(!rt)return 1e18;
        if(curl>=l&&curr<=r){
            return nd[rt].mn;
        }
        int mid=(curl+curr>>1);
        ll ans=1e18;
        if(mid>=l)ckmn(ans,qmn(nd[rt].ls,curl,mid,l,r));
        if(mid<r)ckmn(ans,qmn(nd[rt].rs,mid+1,curr,l,r));
        return ans;
    }
}hjt;
int rt[maxn];
void solve(int id_of_test){
	read(n);
    read(C);
	if(n==1&&C==114)puts("wtf");
    FOR(i,1,n){
        read(a[i]);
    }
    st.init();
    FOR(i,1,n){
        read(b[i]);
        preb[i]=preb[i-1]+b[i];
    }
    hjt.bd(rt[0],1,100000);
    FOR(r,1,n){
        rt[r]=++hjt.ndcnt;
        hjt.nd[rt[r]]=hjt.nd[rt[r-1]];
        int ok=0;
        int efl=1,efr=r;
        while(efl<=efr){
            int mid=(efl+efr>>1);
            if(r-mid+1>=st.qgcd(mid,r)){
                ok=mid;
                efl=mid+1;
            }else{
                efr=mid-1;
            }
        }
        if(!ok)continue;// 不存在合法的 l
        int l=ok;// 最右边的合法的 l
        int _gcd=st.qgcd(l,r);
      //  printf("r = %d\n",r);
        while(l>=1){
        //    printf("l %d _gcd = %d\n",l,_gcd);
            if(r-l+1>=_gcd){
                // 合法，计算答案
                
                ll sum=1ll*_gcd*wb(l,r);
                ll ans=sum;
              //  printf("[%d,%d] sum %d %lld\n",l,r,_gcd,sum);
                ckmn(ans,sum+C+hjt.qmn(rt[l-1],1,100000,1,_gcd));
         //       printf("[%d,%d] ans %lld\n",l,r,ans);
                hjt.chg(rt[r-1],rt[r],1,100000,r-l+1,ans);
          //      printf("[%d,%d] len = %d gcd = %d dp %lld\n",l,r,r-l+1,_gcd,ans);
                /*if(ans+C==-3037806949){
                    printf("[%d,%d] sum %lld\n",l,r,sum);
                }*/
            }
            // 目前 l 是本 gcd 同色块的右端点
            int efl=1,efr=l;
            int ok=l;
            while(efl<=efr){
                int mid=(efl+efr>>1);
                if(st.qgcd(mid,r)!=_gcd){
                    efl=mid+1;
                }else{
                    ok=mid;
                    efr=mid-1;
                }
            }
            // ok 就是本 gcd 同色块的左端点
          //  printf("ok %d\n",ok);
            l=ok-1;
            if(l)_gcd=st.qgcd(l,r);
        }
    }
    printf("%lld\n",hjt.qmn(rt[n],1,100000,1,100000)+C);
}
int main()
{
	int T;
	read(T);
	FOR(_,1,T){
		solve(_);
	}
	return 0;
}