#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<ctime>

#include<cctype>

#include<string>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=1e5+;

int T,n,K,fst[N],nxt[N*],go[N*],tot,cnt,keep;

bool del[N];

inline int R()

{

  char c;int f=;

  for(c=getchar();c<''||c>'';c=getchar());

  for(;c<=''&&c>='';c=getchar())  f=(f<<)+(f<<)+c-'';

  return f;

}

inline void comb(int a,int b)

{

  nxt[++tot]=fst[a],fst[a]=tot,go[tot]=b;

  nxt[++tot]=fst[b],fst[b]=tot,go[tot]=a;

}

inline void pre()

{

  cnt=tot=keep=;

  memset(fst,,sizeof(fst));

  memset(del,false,sizeof(del));

}

inline void dfs(int u,int fa)

{

  for(int e=fst[u];e;e=nxt[e])

  {

    int v=go[e];if(v==fa)  continue;

    dfs(v,u);

    if(!del[v]&&!del[u])

    {

      if(keep<K)

      {

        keep+=;cnt++;

        del[v]=del[u]=true;

      }

    }

  }

}

int main()

{

  //freopen("a.in","r",stdin);

  T=R();int a;

  while(T--)

  {

    n=R(),K=R();pre();

    for(int i=;i<n;i++)  a=R(),comb(i+,a);

    dfs(,);

    if(keep>=K)  cout<<cnt<<"\n";

    else cout<<cnt+(K-keep)<<"\n";

  }

  return ;

}