#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][i] != 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]];
                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--){
                last[v[u[i]]] = u[i];
                calc_tree(u[i],u[i],u.size(),nAL,v,ans,distance,last,depth,position);
            }
            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';
    }
}