#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mod=998244353;
struct edge
{
    int v,nxt;
}e[500005];
int T,n,k,f[100005][505],F[100005][505],t,h[100005],sz[100005],tmp1[505],tmp2[505],g[100005],len[100005];
void add(int u,int v)
{
    e[++t].v=v;
    e[t].nxt=h[u];
    h[u]=t;
}
void dfs1(int u,int fa)
{
    for(int i=0;i<=k+1;i++)
        f[u][i]=0;
    sz[u]=1;
    f[u][1]=1;
    for(int i=h[u];i;i=e[i].nxt)
    {
        int v=e[i].v;
        if(v==fa) continue;
        dfs1(v,u);
        for(int j=0;j<=k+1;j++)
            tmp1[j]=0;
        for(int j=0;j<=min(sz[v],k);j++)
            for(int l=0;l<=min(sz[u],k+1)&&j+l<=k+1;l++)
                tmp1[j+l]=(tmp1[j+l]+1ll*f[v][j]*f[u][l])%mod;
        for(int j=0;j<=k+1;j++)
            f[u][j]=tmp1[j];
        sz[u]+=sz[v];
    }
    f[u][0]=(1ll*f[u][0]+f[u][k]+f[u][k+1])%mod;
}
void dfs2(int u,int fa)
{
    g[u]=sz[u]/k;
//    len[u]=min(sz[u]%k,g[u]);
    for(int i=0;i<=g[u];i++)
        f[u][i]=F[u][i]=0;
//    sz[u]=1;
    f[u][0]=1;
    int nw=1,sumg=0;
    for(int i=h[u];i;i=e[i].nxt)
    {
        int v=e[i].v;
        if(v==fa) continue;
        dfs2(v,u);
        for(int j=0;j<=g[u];j++)
            tmp1[j]=tmp2[j]=0;
        for(int j=0;j<=g[v];j++)
            for(int l=0;l<=sumg&&j+l<=g[u];l++)
            {
                tmp1[j+l]=(tmp1[j+l]+1ll*f[v][j]*f[u][l])%mod;
                tmp2[j+l]=(tmp2[j+l]+1ll*F[v][j]*f[u][l])%mod;
                tmp2[j+l]=(tmp2[j+l]+1ll*f[v][j]*F[u][l])%mod;
            }
        for(int j=0;j<=g[u];j++)
            f[u][j]=tmp1[j],F[u][j]=tmp2[j];
        sumg+=g[v];
    //    sz[u]+=sz[v];
    }
    if(g[u]!=sumg)
    {
        if(sumg<=g[u]-2)
        {
            for(int j=0;j<=g[u];j++)
                f[u][j]=F[u][j]=0;
            return;
        }
        for(int j=0;j<=g[u];j++)
        {
            tmp1[j]=0;
            tmp2[j]=f[u][j];
        }
        for(int t=0;t<=1;t++)
        {
            int nw=sz[u]-(g[u]*k+t);
            if(0<=nw&&nw<=g[u]) tmp1[nw+t]=(tmp1[nw+t]+f[u][nw])%mod;
            nw=sz[u]-((g[u]-1)*k+t);
            if(0<=nw&&nw<=g[u]) tmp2[nw+t]=(tmp2[nw+t]+F[u][nw])%mod;
        }
        for(int j=0;j<=g[u];j++)
            f[u][j]=tmp1[j],F[u][j]=tmp2[j];
    }
    else
    {
        for(int j=0;j<=g[u];j++)
        {
            tmp1[j]=f[u][j];
            tmp2[j]=F[u][j];
        }
        for(int t=1;t<=1;t++)
        {
            int nw=sz[u]-(g[u]*k+t);
            if(0<=nw&&nw<=g[u]) tmp1[nw+t]=(tmp1[nw+t]+F[u][nw])%mod;
        }
        for(int j=0;j<=g[u];j++)
            f[u][j]=tmp1[j],F[u][j]=tmp2[j];
    }
    //printf("u=%d,g=%d\n",u,g[u]);
    //for(int j=0;j<=g[u];j++)
    //    printf("%d %d\n",f[u][j],F[u][j]);
}
void dfs(int u,int fa)
{
    sz[u]=1;
    for(int i=h[u];i;i=e[i].nxt)
    {
        int v=e[i].v;
        if(v==fa) continue;
        dfs(v,u);
        sz[u]+=sz[v];
    }
}
int main()
{
//	freopen("input.txt", "r", stdin);
//	freopen("2.txt", "w", stdout);
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&k);
    //    k=300,n=k*k-3;
        for(int i=0;i<=n;i++)
            h[i]=0;
        t=0;
        for(int i=1;i<n;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
        //    u=i,v=i+1;
            add(u,v);
            add(v,u);
        }
        dfs(1,0);
        if(1ll*k*k<=n)
        {
            dfs1(1,0);
            printf("%d\n",f[1][0]);
            continue;
        }
        dfs2(1,0);
        if(sz[1]%k<=g[1])
            printf("%d\n",f[1][sz[1]%k]);
        else printf("0\n");
    }
}