Untitled

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>

using namespace std;
using namespace __gnu_pbds;

#define fast ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
#define For(i, a, b) for(int i = a; i <= b; i++)
#define RFor(i, a, b) for(int i = a; i >= b; i--)
#define Forr(a, b, c) for(int i = a; i <= b; i+=c)
#define pb push_back
#define fi first
#define se second
#define bit(n, i) ((n>>i)&1)

#ifndef ONLINE_JUDGE
#include "debug.h"
#else
#define debug(...) 42
#define debugArr(...) 42
#endif

typedef long long ll;
typedef pair<int,int> pii; 
typedef tree<int , null_type, less_equal<int> , rb_tree_tag ,tree_order_statistics_node_update>ordered_multiset;

#define LOG 19
#define Maxn 205
const int mod = 1e9+7;

vector<int>vt[Maxn];
set<int>st[Maxn];
pair<int,int>p[Maxn];
int low[Maxn], num[Maxn], timer, par[Maxn], vis[Maxn], sz[Maxn];
int find(int u) {
    if(u == par[u]) return u;
    return par[u] = find(par[u]);
}
void Union(int u, int v) {
    u = find(u);
    v = find(v);
    if(u == v) return;
    if(sz[u] > sz[v]) {
        sz[u] += sz[v];
        par[v] = u;
    } else {
        sz[v] += sz[u];
        par[u] = v;
    }
}
stack<int>stt;
int ans;
void tjr(int u, int v) {
    low[u] = num[u] = ++timer;
    vis[u] = 1;
    stt.push(u);
    for(auto x:vt[u]) {
        if(!vis[x]) {
            tjr(x, u);
            low[u] = min(low[u], low[x]);
        } else if(x != v) {
            low[u] = min(low[u], num[x]);
        }
    }
    if(num[u] == low[u]) {
        int tmp, k, s = 0, cnt = 0;
        map<int,int>mp;
        do {
            tmp = stt.top();
            k = tmp;
            ++cnt;
            for(auto x:st[k]) {
                mp[x]++;
            }
            if(k != u) p[find(u)].se += p[k].se;
            num[k] = low[k] = mod;
            stt.pop();
            Union(tmp, u);
        } while(k != u);
        bool ok = true;
        for(auto x:mp) {
            if(x.se == sz[find(u)]) {
                ok = false;
                break;
            }
        }
        if(ok && cnt > 1) {
            ans = min(ans, p[find(u)].se);
        }
    }
}
int main(){
    fast
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    int t;cin >> t;
    while(t--) {
        timer = 0;
        while(!stt.empty()) stt.pop();
        int n;cin >> n;
        For(i, 1, n) cin >> p[i].fi;
        For(i, 1, n) cin >> p[i].se;
        For(i, 1, n) {
            st[i].clear();
            vt[i].clear();
            par[i] = i;
            vis[i] = 0;
            sz[i] = 1;
        }
        ans = 1e9;
        For(i, 1, n) {
            if(p[i].fi == 1) {
                ans = min(ans, p[i].se);
                continue;
            }
            For(j, 1, i-1) {
                if(__gcd(p[i].fi, p[j].fi) == 1) ans = min(ans, p[i].se+p[j].se); 
            }
        }
        For(i, 1, n) {
            For(j, 2, sqrt(p[i].fi)) {
                while(p[i].fi%j == 0) {
                    st[i].insert(j);
                    p[i].fi /= j;
                }
            }
            if(p[i].fi != 1) st[i].insert(p[i].fi);
        }
        For(i, 1, n) {
            For(j, 1, i-1) {
                for(auto x:st[i]) {
                    if(st[j].count(x)) {
                        vt[i].pb(j);
                        vt[j].pb(i);
                    }
                }
            }
        }
        For(i, 1, n) {
            if(!vis[i]) tjr(i, 0);
        }
        if(ans == 1e9) {
            cout << -1 << endl;
            continue;
        }
        cout << ans << endl;
    }
    return 0;
}