#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
using namespace std;
using namespace __gnu_pbds;
using ll=long long;
using ld=long double;
using vi=vector<int>;
template<class T> using oset =tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update> ;
//上
const int N = 200005;
const ll inf = 1000000000000000000;
int par[N][20];
int par1[N][20];
ll k;
map<ll,ll>mp;
void init_par(vector<int> &parent){
int n = parent.size();
for(int i = 0; i < n;i++){
if(parent[i] == -1) par[i][0] = i;
else par[i][0] = parent[i];
}
for(int i = 1; i < 20; i++){
for(int j = 0; j < n; j++) par[j][i] = par[par[j][i-1]][i-1];
}
}
void init_par2(vector<int> &parent){
int n = parent.size();
for(int i = 0; i < n;i++){
par1[i][0] = parent[i];
}
for(int i = 1; i < 20; i++){
for(int j = 0; j < n; j++) if(parent[j] != -1) par1[j][i] = par1[par1[j][i-1]][i-1];
}
}
ll jump(int x,int y){
ll su = 1;
for(int i = 19; i>= 0;i--){
if(par[x][i] != y&&par[x][y] != x) x = par[x][i],su +=(1<<i);
}
return su;
}
int move(int x,ll dis){
for(int i = 0; i < 20 ; i++){
if(dis&(1<<i)) x = par[x][i];
}
return x;
}
int move2(int x,ll dis){
for(int i = 0; i < 20 ; i++){
if(dis&(1<<i)) x = par1[x][i];
}
return x;
}
void toposort(int x,vector<vector<int>> &AL,vector<int>&vis,vector<int> &topo){
vis[x] = 1;
for(auto &u: AL[x]){
if(vis[u] == 0) toposort(u,AL,vis,topo);
}
topo.push_back(x);
}
void dfs(int x,int c,vector<vector<int>> &AL,vector<int> &scc){
scc[x] = c;
for(auto &u: AL[x]){
if(scc[u] == -1) dfs(u,c,AL,scc);
}
}
void create_ancester_tree(int x,int root,vector<int> &v,vector<vector<int>> &nAL,vector<int> & parent,vector<int> &last,vector<int>&depth,vector<int>&toerase){
if(x != root){
if(last[v[x]] != -1) parent[x] = last[v[x]];
else parent[x] = root;
last[v[x]] = x;
}
toerase.push_back(v[x]);
for(auto &u: nAL[x]){
depth[u] = depth[x] + 1;
create_ancester_tree(u,root,v,nAL,parent,last,depth,toerase);
}
if(x!=root) last[v[x]] = parent[x];
}
vector<ll> calc_cycle(int x,vector<vector<int>> &AL,vector<int> &v,vector<ll> &ans,vector<ll> &distance,vector<int>&position,vector<int>&last,vector<int>&parent){
ll sz = 1;
int p1 = x;
int p2 = x;
map<int,ll> val;
ll mx = 1;
val[v[x]]++;
position[p1] = sz-1;
last[v[p1]] = -1;
vector<ll> cyc = {x};
while(AL[p1][0] != x){
p1 =AL[p1][0],sz++;
position[p1] = sz-1;
last[v[p1]] = -1;
cyc.push_back(p1);
mx = max(mx,++val[v[p1]]);
}
ll vueltas = ((k+mx-1)/mx-1);
for(auto &u:val){
u.second = u.second*vueltas;
}
p1 = x;
ll d = 0;
val[v[p1]]++;
for(int i = 0; i < sz;i++){
while(true){
if(val[v[p2]] == k){
distance[p1] = vueltas*sz+d;
ans[p1] = v[p2];
break;
}else{
p2 = AL[p2][0];
val[v[p2]]++;
d++;
}
}
d--;
val[v[p1]]--;
p1 = AL[p1][0];
}
p1 = x;
for(int i = 0; i <2*sz;i++){
if(last[v[p1]] != -1){
parent[last[v[p1]]] = p1;
}
last[v[p1]] = p1;
p1 = AL[p1][0];
}
return cyc;
}
void calc_tree(int x,int root,ll sz,vector<vector<int>> &AL,vector<int> &v,vector<ll> & ans,vector<ll> &distance,vector<int> &last,vector<int>&depth,vector<int>&position){
for(auto &u: AL[x]){
ll steps = 0;
ll su = 0;
ll toroot = jump(u,root);
if(toroot >= k){
su = depth[u]-depth[move(u,k-1)];
}else{
if(last[v[u]] !=-1){
steps = toroot;
su = depth[u];
if(position[last[v[u]]] >= position[root]){
su +=position[last[v[u]]] -position[root];
}else{
su += sz-position[root]+position[last[v[u]]];
}
ll many = mp[v[u]];
assert(many != 1)
ll o = (k-steps +many-1)/many-1;
steps += o* many;
su+=o*sz;
ll extra =move2(last[v[u]],k-steps-1);
if(position[extra] >= position[last[v[u]]]){
su += position[extra]-position[last[v[u]]];
}else su += sz-position[last[v[u]]]+position[extra];
}else su = inf;
}
if(su <distance[x] +1){
distance[u] = su;
ans[u] = v[u];
}else{
distance[u] = distance[x]+1;
ans[u] = ans[x];
}
calc_tree(u,root,sz,AL,v,ans,distance,last,depth,position);
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while(t--){
ll n; cin >> n >> k;
vector<vector<int>> AL(n),AL_T(n);
vector<int> v(n),scc(n,-1),vis(n),parent(n,-1),last(n,-1),depth(n),position(n),aux(n,-1);
vector<ll> ans(n,-1),distance(n);
vector<int>topo;
FOR(i,0,n){cin >> v[i];v[i]--;}
FOR(i,0,n){
int x; cin >> x;
x--; AL[i].push_back(x); AL_T[x].push_back(i);
}
for(int i = 0; i < n; i++){
if(!vis[i]) toposort(i,AL,vis,topo);
}
reverse(topo.begin(),topo.end());
int cur = 0;
for(auto &u: topo){
if(scc[u] == -1) dfs(u,cur++,AL_T,scc);
}
vector<vector<int>> nAL(n);
for(int i = 0; i < n; i++){
if(scc[AL[i][0]] != scc[i]) nAL[AL[i][0]].push_back(i);
}
for(int i = 0; i < n; i++){
if(scc[AL[i][0]] == scc[i]){
vector<int> toerase;
create_ancester_tree(i,i,v,nAL,parent,last,depth,toerase);
for(auto &u:toerase) last[u] = -1;
}
}
init_par(parent);
for(int i = 0; i < n; i++) parent[i] = -1;
vector<vector<ll>> temp;
for(int i = 0; i < n; i++){
if(scc[AL[i][0]] == scc[i] && ans[i] == -1){
temp.push_back(calc_cycle(i,AL,v,ans,distance,position,last,parent));
}
}
init_par2(parent);
for(int i = 0; i < n; i++) last[i] = -1;
for(auto &u: temp){
mp.clear();
for(int i = (int)u.size()-1; i >= 0;i--){
last[v[u[i]]] = u[i];
mp[v[u[i]]]++;
}
for(int i = (int)u.size()-1; i >= 0;i--){
calc_tree(u[i],u[i],u.size(),nAL,v,ans,distance,last,depth,position);
last[v[u[i]]] = u[i];
}
for(int i = 0; i < u.size();i++) last[v[u[i]]] = -1;
}
ll re = 0;
// trace(ans);
for(ll i = 1; i <= n;i++) re += i*(ans[i-1]+1);
cout <<re<<'\n';
}
}