#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define N 100000

int i,j,k,n,t;
ll f[N+50],a[N+50],b[N+50],res,c;

void add(int x,ll y){for(;x<=n;x+=(-x&x)){f[x]=min(f[x],y);}}
ll get(int x,ll y=0){for(;x;x-=(-x&x)){y=min(y,f[x]);}return y;}
vector<tuple<ll,ll,ll,ll> > q[N+50];
vector<pair<ll,ll> > q2[N+50];

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	int CNM; cin>>CNM;
	
	while(CNM--){
		map<int,int> NMSL,NMSL2;
		
		cin>>n>>c; res=1e18;
		
		for(i=1;i<=n;i++)cin>>a[i];
		for(i=1;i<=n;i++){
			cin>>b[i]; b[i]+=b[i-1];
		}
		
		for(i=1;i<=n;i++){
			NMSL2={};
			for(auto [x,y]:NMSL)NMSL2[gcd(x,a[i])]=y;
			NMSL2[a[i]]=i; NMSL=NMSL2;
			int lst=0;
			for(auto [x,y]:NMSL){
				k=min(y,i-x+1);
				if(k>lst){
					q[k-1].push_back({i,i-k+1,x,c+(b[i]-b[k-1])*x});
				}
				lst=y;
			}
		}
		
		fill(f,f+n+1,1e18);
		for(i=0;i<=n;i++){
			for(auto [x,y]:q2[i]){res=min(res,y); add(x,y);}
			for(auto [x,y,p,w]:q[i])q2[x].push_back({y,get(p)+w});
		}
		
		cout<<res<<'\n';
		for(i=0;i<=n;i++)q[i]={},q2[i]={};
	}
}