#include <bits/stdc++.h>
using namespace std;
const bool test=false;
typedef long long ll;
ll solve()
{
    int n,k;cin>>n>>k;
    vector<int> v(n+1),to(n+1);
    for(int i=1;i<=n;i++)cin>>v[i];
    for(int i=1;i<=n;i++)cin>>to[i];
    vector<pair<int,vector<int>>> sub_tree;//root,circle_list
    vector<vector<int>> ve(n+1);
    {
        vector<int> cnt(n+1);
        for(int i=1;i<=n;i++)cnt[to[i]]++;
        queue<int> qu;
        for(int i=1;i<=n;i++)if(cnt[i]==0)qu.push(i);
        vector<int> vis(n+1);
        while(!qu.empty()){
            int x=qu.front();qu.pop();
            vis[x]=1;
            ve[to[x]].push_back(x);
            if(--cnt[to[x]]==0)qu.push(to[x]);
        }
        for(int i=1;i<=n;i++)if(!vis[i]){
            vector<int> lis,c;
            int x=i;
            while(!vis[x]){
                vis[x]=1;
                lis.push_back(x);
                c.push_back(v[x]);
                x=to[x];
            }
            for(int i=0;i+1<lis.size();i++)ve[lis[i+1]].push_back(lis[i]);
            sub_tree.emplace_back(lis.back(),c);
        }
    }
    vector<int> ans(n+1);
    vector<ll> cnt(n+1),num(n+1,-1);//cnt
    for(auto &[root,lis]:sub_tree){
        if(test){
            cout<<"root="<<root<<endl;
            cout<<"lis :";;for(auto it:lis)cout<<it<<" ";;cout<<endl;
            // for(int i=1;i<=n;i++)cout<<cnt[i]<<" ";;cout<<endl;
            // for(int i=1;i<=n;i++)cout<<num[i]<<" ";;cout<<endl;
        }
        set<pair<ll,int>> s;
        map<int,vector<int>> ma;
        map<int,vector<int>> sta;
        vector<int> all;
        function<void(int,int)> dfs = [&](int x,int d){
            all.push_back(v[x]);
            ll prans=num[v[x]];
            sta[v[x]].push_back(d);
            if(prans!=-1)s.erase({prans,v[x]});
            {//recal num[v[x]]
                if(sta[v[x]].size()>=k){
                    num[v[x]]=d-sta[v[x]][sta[v[x]].size()-k]+1;
                }
                else if(ma.find(v[x])!=ma.end()){
                    int kk=k-sta[v[x]].size();
                    // cout<<"x="<<x<<" v[x]="<<v[x]<<" kk="<<kk<<" cnt="<<cnt[v[x]]<<endl;
                    // for(auto it:ma[v[x]])cout<<it<<" ";;cout<<endl;
                    if(kk%cnt[v[x]]==0){
                        num[v[x]]=(ll)(kk/cnt[v[x]]-1)*(ll)lis.size()+ma[v[x]].back();
                    }
                    else{
                        num[v[x]]=(ll)(kk/cnt[v[x]])*(ll)lis.size()+ma[v[x]][kk%cnt[v[x]]-1];
                    }
                }
            }
            if(num[v[x]]!=-1)s.insert({num[v[x]],v[x]});
            if(test){
                cout<<"x="<<x<<" d="<<d<<endl;
                cout<<"s :";for(auto [x,y]:s)cout<<x+d<<","<<y<<" ";;cout<<endl;
            }
            ans[x]=get<1>(*s.begin());
            for(auto it:ve[x])dfs(it,d+1);

            sta[v[x]].pop_back();
            if(num[v[x]]!=-1)s.erase({num[v[x]],v[x]});
            num[v[x]]=prans;
            if(prans!=-1)s.insert({prans,v[x]});
        };
        for(int i=0;i<lis.size();i++)ma[lis[i]].push_back(i+1),cnt[lis[i]]++;
        for(auto &it:ma){
            int x=it.first;
            if(k%cnt[x]==0){
                num[x]=(ll)(k/cnt[x]-1)*(ll)lis.size()+ma[x].back();
            }
            else{
                num[x]=(ll)(k/cnt[x])*(ll)lis.size()+ma[x][k%cnt[x]-1];
            }
            s.insert({num[x],x});
        }

        dfs(root,1);
        for(auto it:lis)cnt[it]=0,num[it]=-1;
        for(auto it:all)cnt[it]=0,num[it]=-1;
    }
    
    
    {
        ll res=0;
        for(int i=1;i<=n;i++)res+=(ll)ans[i]*i;
        if(test){cout<<"ans :";for(int i=1;i<=n;i++)cout<<ans[i]<<" ";;cout<<endl;}
        return res;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;cin>>T;while(T--)cout<<solve()<<"\n";
    return 0;
}