#include #include #include #include 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 pii; typedef tree , rb_tree_tag ,tree_order_statistics_node_update>ordered_multiset; #define LOG 19 #define Maxn 205 const int mod = 1e9+7; vectorvt[Maxn]; setst[Maxn]; pairp[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; } } stackstt; 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; mapmp; 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; }

Untitled