#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5;

int n, a[N], b[N], col[N << 1], c[2];
vector<int> G[N << 1];

void dfs(int x) {
    ++c[col[x]];
    for (auto v : G[x]) if (!~col[v]) col[v] = !col[x], dfs(v);
}

int dfn[N << 1], low[N << 1], mx;

pair<int, int> Tarjan(int x, int fa = 0) {
    dfn[x] = low[x] = ++dfn[0];
    pair<int, int> p = make_pair(!col[x], col[x]);
    for (auto v : G[x]) if (v != fa) {
        if (!dfn[v]) {
            pair<int, int> q = Tarjan(v, x);
            p.first += q.first, p.second += q.second;
            low[x] = min(low[x], low[v]);
        } else low[x] = min(low[x], dfn[v]);
    } else fa = 0;
    if (low[x] == dfn[x]) {
        mx = max(mx, min(c[0], c[1]) - min(p.first, p.second) - min(c[0] - p.first, c[1] - p.second));
    }
    return p;
}

multiset< pair<int, pair<int, int> > > S;
pair<int, int> cz;

pair<int, int> Tarj(int x, int fa = 0) {
    dfn[x] = low[x] = ++dfn[0];
    int tv = fa;
    pair<int, int> p = make_pair(!col[x], col[x]);
    for (auto v : G[x]) if (v != fa) {
        if (!dfn[v]) {
            pair<int, int> q = Tarj(v, x);
            p.first += q.first, p.second += q.second;
            low[x] = min(low[x], low[v]);
        } else low[x] = min(low[x], dfn[v]);
    } else fa = 0;
    if (!tv) return p;
    if (low[x] == dfn[x]) {
        S.erase(S.find(make_pair(cz.first - cz.second, cz)));
        S.insert(make_pair(p.first - p.second, p));
        int v1, v2, v3, v4;
        v1 = cz.first - p.first, v2 = cz.second - p.second;
        tie(v3, v4) = (*S.begin()).second;
        mx = max(mx, min(v1 + v3, v2 + v4) - min(v1, v2) - min(v3, v4) + min(p.first, p.second) + min(cz.first - p.first, cz.second - p.second) - min(cz.first, cz.second));
        v1 = cz.first - p.first, v2 = cz.second - p.second;
        tie(v3, v4) = (*--S.end()).second;
        mx = max(mx, min(v1 + v3, v2 + v4) - min(v1, v2) - min(v3, v4) + min(p.first, p.second) + min(cz.first - p.first, cz.second - p.second) - min(cz.first, cz.second));
        S.erase(S.find(make_pair(p.first - p.second, p)));
        S.insert(make_pair((cz.first - p.first) - (cz.second - p.second), make_pair(cz.first - p.first, cz.second - p.second)));
        v1 = p.first, v2 = p.second;
        tie(v3, v4) = (*S.begin()).second;
        mx = max(mx, min(v1 + v3, v2 + v4) - min(v1, v2) - min(v3, v4) + min(p.first, p.second) + min(cz.first - p.first, cz.second - p.second) - min(cz.first, cz.second));
        v1 = p.first, v2 = p.second;
        tie(v3, v4) = (*--S.end()).second;
        mx = max(mx, min(v1 + v3, v2 + v4) - min(v1, v2) - min(v3, v4) + min(p.first, p.second) + min(cz.first - p.first, cz.second - p.second) - min(cz.first, cz.second));
        S.erase(S.find(make_pair((cz.first - p.first) - (cz.second - p.second), make_pair(cz.first - p.first, cz.second - p.second))));
        S.insert(make_pair(cz.first - cz.second, cz));
    } else {
        S.erase(S.find(make_pair(cz.first - cz.second, cz)));
        if (!S.empty()) {
            int v1, v2, v3, v4;
            v1 = cz.first, v2 = cz.second;
            tie(v3, v4) = (*S.begin()).second;
            mx = max(mx, min(v1 + v3, v2 + v4) - min(v1, v2) - min(v3, v4));
            v1 = cz.first, v2 = cz.second;
            tie(v3, v4) = (*--S.end()).second;
            mx = max(mx, min(v1 + v3, v2 + v4) - min(v1, v2) - min(v3, v4));
        }
        S.insert(make_pair(cz.first - cz.second, cz));
    }
    return p;
}

signed main() {
    int T, opt; scanf("%d%d", &T, &opt);
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
        for (int i = 1; i <= n; ++i) scanf("%d", &b[i]);
        for (int i = 1; i <= n << 1; ++i) G[i].clear(), col[i] = -1;
        for (int i = 1; i <= n; ++i) {
            G[a[i]].push_back(b[i] + n), G[b[i] + n].push_back(a[i]);
        }
        if (opt == 0) {
            int res = 0;
            for (int i = 1; i <= n << 1; ++i) if (!~col[i]) {
                c[0] = c[1] = 0, col[i] = 0, dfs(i), res += min(c[0], c[1]);
            }
            printf("%d\n", res);
        } else if (opt == 1) {
            if (n == 1) {
                puts("1");
                continue;
            }
            int res = 0;
            for (int i = 0; i <= n << 1; ++i) dfn[i] = 0;
            mx = 0;
            for (int i = 1; i <= n << 1; ++i) if (!~col[i]) {
                c[0] = c[1] = 0, col[i] = 0, dfs(i), res += min(c[0], c[1]);
                Tarjan(i);
            }
            printf("%d\n", res - mx);
        } else {
            int res = 0;
            S.clear();
            vector< pair<int, int> > arr;
            for (int i = 1; i <= n << 1; ++i) if (!~col[i]) {
                c[0] = c[1] = 0, col[i] = 0, dfs(i), res += min(c[0], c[1]);
                S.insert(make_pair(c[0] - c[1], make_pair(c[0], c[1])));
                arr.push_back(make_pair(c[0], c[1]));
            }
            for (int i = 0; i <= n << 1; ++i) dfn[i] = 0;
            mx = 0;
            int now = 0;
            for (int i = 1; i <= n << 1; ++i) if (!dfn[i]) {
                cz = arr[now++];
                Tarj(i);
            }
            printf("%d\n", res + mx);
        }
    }
    return 0;
}