记录

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e4 + 5;

int n, m, s, t, inc[N], ans, tot, p[N];

bool vis[N]; 

struct Edge {
	int to, w, bk;
}; vector<Edge> nbr[N];

struct Pre {
	int x, i;
} pre[N];

void add(int x, int y, int w) {
	nbr[x].push_back((Edge){y, w, nbr[y].size()});
	nbr[y].push_back((Edge){x, 0, nbr[x].size() ^ 1});
}

void update() {
	int cur = t;
	while (cur != s) {
		int lasx = pre[cur].x, lasi = pre[cur].i;
		nbr[lasx][lasi].w -= inc[t];
		nbr[cur][nbr[lasx][lasi].bk].w += inc[t];
		cur = lasx;
	}
	ans += inc[t];
}

bool bfs() {
	memset(vis, 0, sizeof vis);
	queue<int> q;
	q.push(s);
	vis[s] = true;
	inc[s] = INT_MAX;
	while (!q.empty()) {
		int cur = q.front(); q.pop();
		for (int i = 0; i < nbr[cur].size(); i++) {
			auto e = nbr[cur][i];
			int nxt = e.to, w = e.w;
			if (vis[nxt] || !w) continue;
			vis[nxt] = true;
			inc[nxt] = min(inc[cur], w);
			pre[nxt] = {cur, i};
			q.push(nxt);
			if (nxt == t) return true;
        }   
    }
	return false;
}

void work(int x, int num, int flag) {
    if (!flag) add(s, x, 1);
	for (int i = 2; i * i <= num; i++) {
		if (num % i != 0) continue;
		if (!p[i]) p[i] = ++ tot;
		while (num % i == 0) num /= i;
		if (!flag) add(x, p[i] + n + m, 1);
		else add(p[i] + n + m, x, 1);
	}   
	if (num > 1) {
        if (!p[num]) p[num] = ++tot;
		if (!flag) add(x, p[num] + n + m, 1);
		else add(p[num] + n + m, x, 1);
	}
}

void init() {
	for (int i = 0; i < N; i++) {
		nbr[i].clear();
		inc[i] = p[i] = 0;
		pre[i] = {0, 0};
	}
	tot = ans = 0;
}

void solve() {
	init();
	cin >> m >> n;
	s = 0;
	for (int i = 1; i <= m; i++) {
		int x; cin >> x;
		work(i, x, 0);
	} 
	for (int i = 1; i <= n; i++) {
		int x; cin >> x;
		work(i + m, x, 1);
	}
	t = n + m + tot + 1;
	for (int i = 1; i <= n; i++)
		add(i + m, t, 1);
	while (bfs()) update();
	cout << ans << "\n";
}

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
	int T; cin >> T;
	while (T--) solve();
	return 0;
}
// Stone_Xz