#include<bits/stdc++.h>

using namespace std;   

#define forn(i, n) for(int i = 0; i < int(n); i++)
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

typedef long long li;

const li INF64 = 1e18;

int n, k;
vector<int> a, g;

bool read() {
	if (!(cin >> n >> k))
		return false;
	a.resize(n);
	forn(i, n){
		cin >> a[i];
		--a[i];
	}
	g.resize(n);
	forn(i, n){
		cin >> g[i];
		--g[i];
	}
	--k;
	return true;
}

vector<vector<int>> gg;
vector<char> used;
vector<pair<int, li>> ans;

vector<pair<int, int>> st;
vector<int> nxt;
vector<char> cyc;

const int LOGN = 30;
vector<vector<int>> up;
vector<vector<li>> uplen;

void extend(int u){
	up[u][0] = (nxt[a[u]] == -1 ? n : st[nxt[a[u]]].first);
	uplen[u][0] = (nxt[a[u]] == -1 ? 0 : sz(st) - nxt[a[u]]);
	fore(i, 1, LOGN){
		up[u][i] = up[up[u][i - 1]][i - 1];
		uplen[u][i] = uplen[u][i - 1] + uplen[up[u][i - 1]][i - 1];
	}
	st.push_back({u, nxt[a[u]]});
	nxt[a[u]] = sz(st) - 1;
}

void pop(){
	int u = st.back().first;
	nxt[a[u]] = st.back().second;
	st.pop_back();
}

void dfs(int v, int p){
	used[v] = true;
	extend(v);
	ans[v] = ans[p];
	++ans[v].second;
	int w = v;
	li dist = 1;
	forn(i, LOGN) if ((k >> i) & 1){
		dist += uplen[w][i];
		w = up[w][i];
	}
	//cerr << v + 1 << " " << dist << " " << ans[v].first + 1 << " " << ans[v].second << endl;
	if (w != n && dist < ans[v].second){
		ans[v] = {a[v], dist};
	}
	for (int u : gg[v]) if (!cyc[u]){
		dfs(u, v);
	}
	pop();
}

vector<li> cnt;

void calc(int v){
	int len = 1;
	int u = g[v];
	cyc[u] = true;
	vector<int> cur({v});
	while (u != v){
		cur.push_back(u);
		u = g[u];
		cyc[u] = true;
		++len;
	}
	reverse(cur.begin(), cur.end());
	forn(i, 2 * len){
		int u = cur[i % len];
		extend(u);
	}
	auto check = [&](li d){
		for (int v : cur) cnt[a[v]] = 0;
		for (int v : cur) cnt[a[v]] += d / len;
		forn(i, d % len) ++cnt[a[cur[len - i - 1]]];
		li mx = 0;
		for (int v : cur) mx = max(mx, cnt[a[v]]);
		if (mx <= k) return false;
		//cerr << d << " : ";
		//for (li x : cnt) cerr << x << " ";
		//cerr << endl;
		ans[cur.back()].second = d;
		ans[cur.back()].first = a[cur[(len - d % len) % len]];
		return true;
	};
	li l = 0, r = n * li(k);
	while (l <= r){
		li m = (l + r) / 2;
		if (check(m))
			r = m - 1;
		else
			l = m + 1;
	}
	//cerr << len << endl;
	//for (int v : cur) cerr << v + 1 << " ";
	//cerr << endl;
	//cerr << cur.back() + 1 << " " << ans[cur.back()].first + 1 << " " << ans[cur.back()].second << endl;
	
	//for (auto [v, lst] : st) cerr << "(" << v + 1 << " " << lst << ") ";
	//cerr << endl;
	forn(i, len){
		int u = cur[i];
		dfs(u, cur[(i - 1 + len) % len]);
		extend(u);
	}
	
	//cerr << ans[cur.back()].first + 1 << " " << ans[cur.back()].second << endl;
	//forn(i, n) cerr << int(used[i]);
	//cerr << endl;
	//cerr << "!";
	//exit(0);
	for (auto [x, _] : st)
		nxt[a[x]] = -1;
	st.clear();
}

void solve() {
	up.assign(n + 1, vector<int>(LOGN, n));
	uplen.assign(n + 1, vector<li>(LOGN, 0));
	cyc.assign(n, false);
	gg.assign(n, {});
	forn(i, n) gg[g[i]].push_back(i);
	
	cnt.assign(n, 0);
	used.assign(n, false);
	vector<char> used2(n);
	ans.assign(n, {-1, INF64});
	nxt.assign(n, -1);
	forn(i, n) if (!used[i]){
		int v = i;
		while (!used2[v]){
			used2[v] = true;
			v = g[v];
		}
		calc(v);
	}
	
	li res = 0;
	//forn(i, n) cerr << ans[i].first + 1 << " " << ans[i].second << endl;
	forn(i, n) res += (ans[i].first + 1) * li(i + 1);
	cout << res << '\n';
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	cin >> t;
	forn(i, t) {
	 	read();
		solve();
	}
}