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

const int N = 4e5 + 5;

int T, k, n, tot, totd, ans, sum, mA, mB, h[N], a[N], b[N], dfn[N], low[N], rt[N], A[N], B[N], bri[N];
bool vis[N];

struct Edge {
	int v, nxt;
} e[N * 2];

void add(int u, int v) {
	e[++tot].v = v;
	e[tot].nxt = h[u];
	h[u] = tot;
}

void dfs(int u, int fa, int t) {
	vis[u] = 1;
	dfn[u] = ++totd;
	low[u] = totd;
	rt[u] = t;
	A[u] = u <= n;
	B[u] = u > n;
	bri[u] = -1;
	for (int i = h[u]; i; i = e[i].nxt) {
		if ((i ^ 1) == fa) {
			continue;
		}
		int v = e[i].v;
		if (!vis[v]) {
			dfs(v, i, t);
			if (low[v] > low[u]) {
				bri[v] = u;
			}
			low[u] = min(low[u], low[v]);
			A[u] += A[v];
			B[u] += B[v];
		} else {
			low[u] = min(low[u], dfn[v]);
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> T >> k;
	while (T--) {
		cin >> n;
		for (int i = 1; i <= n; i++) {
			cin >> a[i];
		}
		for (int i = 1; i <= n; i++) {
			cin >> b[i];
		}
		if (n == 1) {
			cout << "1\n";
			continue;
		}
		tot = 1;
		for (int i = 1; i <= n * 2; i++) {
			h[i] = 0;
		}
		for (int i = 1; i <= n; i++) {
			int u = a[i], v = b[i] + n;
			add(u, v);
			add(v, u);
		}
		totd = 0;
		for (int i = 1; i <= n * 2; i++) {
			vis[i] = 0;
			bri[i] = 0;
		}
		for (int i = 1; i <= n * 2; i++) {
			if (!vis[i]) {
				dfs(i, 0, i);
			}
		}
		sum = 0;
		for (int i = 1; i <= n * 2; i++) {
			if (rt[i] == i) {
				sum += min(A[i], B[i]);
			}
		}
		ans = sum;
		mA = 0;
		mB = 0;
		for (int i = 1; i <= n * 2; i++) {
			if (rt[i] == i) {
				mA = max(mA, A[i]);
				mB = max(mB, B[i]);
			}
		}
		if (k == 2) {
			for (int i = 1; i <= n; i++) {
				int u = a[i], v = b[i] + n;
				if (bri[u] == v) {
					int uA = A[u], uB = B[u];
					int vA = A[rt[u]] - A[u], vB = B[rt[u]] - B[u];
					int now = sum - min(A[rt[u]], B[rt[u]]) + min(uA, uB) + min(vA, vB);
					if (uA >= uB) {
						ans = max(ans, now + min(uA - uB, mB));
					} else {
						ans = max(ans, now + min(uB - uA, mA));
					}
					if (vA >= vB) {
						ans = max(ans, now + min(vA - vB, mB));
					} else {
						ans = max(ans, now + min(vB - vA, mA));
					}
				} else if (bri[v] == u) {
					int uA = A[rt[v]] - A[v], uB = B[rt[v]] - B[v];
					int vA = A[v], vB = B[v];
					int now = sum - min(A[rt[v]], B[rt[v]]) + min(uA, uB) + min(vA, vB);
					if (uA >= uB) {
						ans = max(ans, now + min(uA - uB, mB));
					} else {
						ans = max(ans, now + min(uB - uA, mA));
					}
					if (vA >= vB) {
						ans = max(ans, now + min(vA - vB, mB));
					} else {
						ans = max(ans, now + min(vB - vA, mA));
					}
				} else {
					if (A[u] >= B[u]) {
						ans = max(ans, sum + min(A[u] - B[u], mB));
					} else {
						ans = max(ans, sum + min(B[u] - A[u], mA));
					}
				}
			}
		} else if (k == 1) {
			for (int i = 1; i <= n; i++) {
				int u = a[i], v = b[i] + n;
				if (bri[u] == v) {
					int uA = A[u], uB = B[u];
					int vA = A[rt[u]] - A[u], vB = B[rt[u]] - B[u];
					int now = sum - min(A[rt[u]], B[rt[u]]) + min(uA, uB) + min(vA, vB);
					ans = min(ans, now);
				} else if (bri[v] == u) {
					int uA = A[rt[v]] - A[v], uB = B[rt[v]] - B[v];
					int vA = A[v], vB = B[v];
					int now = sum - min(A[rt[v]], B[rt[v]]) + min(uA, uB) + min(vA, vB);
					ans = min(ans, now);
				}
			}
		}
		cout << ans << '\n';
	}

	return 0;
}