#define _CRT_SECURE_NO_WARNINGS
#pragma comment(linker, "/stack:16777216")
#include <string>
#include <vector>
#include <map>
#include <list>
#include <iterator>
#include <set>
#include <queue>
#include <iostream>
#include <sstream>
#include <stack>
#include <deque>
#include <cmath>  
#include <memory.h>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <utility>
#include <time.h>
#include <bitset>
#include <random>
using namespace std;

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
#define ITER(it, a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(A,value) memset(A,value,sizeof(A))

#define ALL(V) V.begin(), V.end()
#define SZ(V) (int)V.size()
#define PB push_back
#define MP make_pair
const double PI=acos(-1.0);

typedef long long Int;
typedef long long LL;
typedef unsigned long long UINT;
typedef vector <int> VI;
typedef pair <int, int> PII;
typedef pair <double, double> PDD;

const int INF = 1000 * 1000 * 1000 + 7;
const LL LINF = INF * (LL) INF;

const int MAX = 100007;
const int CNT = 21;
const int MAX2 = 24000000;
const int LEN = 21;
const int BASE = 1000000000;

const int MOD = 998244353;

int n, k;
VI G[MAX];
int C[MAX];
VI V[MAX];
VI P;
int Q[MAX];

int T[MAX][CNT];
int RS[MAX][CNT];

int TT[MAX][CNT][2];

void dfs(int v, int p)
{
  Q[v] = p;
  C[v] = 1;
  FOR (k,0,SZ(G[v]))
  {
    int to = G[v][k];
    if (to == p) continue;
    dfs(to, v);
    C[v] += C[to];
    V[v].PB(to);
  }

  P.PB(v);
}

void add(int& x, int y)
{
  x += y;
  if (x >= MOD) x -= MOD;
}

int solveSmall()
{
  FOR (i,0,n)
  {
    int v = P[i], s = 1;

    FOR (j,0,SZ(V[v])+1)
      FOR (t,0,CNT)
        T[j][t] = 0;

    T[0][1] = 1;

    FOR (j,0,SZ(V[v]))
    {
      int to = V[v][j];

      FOR (t0,0,s+1)
        if (T[j][t0] != 0)
          FOR (t1,0,min(C[to], k)+1)
            if (t0+t1 <= k+1)
            {
              int d = (Int)RS[to][t1] * T[j][t0] % MOD;
              add(T[j+1][t0+t1], d);
            }

      s += C[to];
    }


    // FOR (t,0,k+2)
    //   cout << v << ' ' << t << ' ' << T[SZ(V[v])+1][t] << endl;

    // cout << endl;

    FOR (j,0,k+1)
      RS[v][j] = T[SZ(V[v])][j];
    add(RS[v][0], T[SZ(V[v])][k]);
    add(RS[v][0], T[SZ(V[v])][k+1]);
  }

  return RS[0][0];
}

int solveLarge()
{
  int res = 0;
  
  FOR (i,0,n)
  {
    int v = P[i], s = 0;

    FOR (j,0,SZ(V[v])+1)
      FOR (t,0,CNT)
        FOR (q,0,2)
            TT[j][t][q] = 0;

    TT[0][0][0] = 1;

    FOR (j,0,SZ(V[v]))
    {
      int to = V[v][j];

      FOR (t0,0,min(CNT, s/k+2))
      FOR (q0,0,2)
        if (TT[j][t0][q0] != 0)
          FOR (t1,0,min(CNT, C[to]/k+2))
            if (t0+t1 < CNT && t1 <= C[to])
            {
              int c0 = (s-t0) % k;
              int c1 = (C[to]-t1) % k;

              if (c0 == 0 && c1 > 0 && q0) continue;

              int q1 = q0;
              if (c1 != 0) q1 = 1;

              if (c0 + c1 <= k)
              {
                int d = (Int)RS[to][t1] * TT[j][t0][q0] % MOD;
                add(TT[j+1][t0+t1][q1], d);
              }
            }

      s += C[to];
    }

    // FOR (t,0,6)
    // FOR (q,0,2)
    //   cout << v << ' ' << t << ' ' << q << ' ' <<  TT[SZ(V[v])][t][q] << endl;
    

    FOR (j,0,CNT)
      FOR (q,0,2)
      {
        int cc = C[v]-1;

        if (j > cc) continue;
        int t = (cc-j) % k;

        if (t > 0 && t < k-1)
          add(RS[v][j], TT[SZ(V[v])][j][q]);
        else
        if (t == k-1)
        {
          if (q)
          {
            add(RS[v][j], TT[SZ(V[v])][j][q]);

            if (Q[v] != -1 && SZ(V[Q[v]]) == 1)
            {
              add(RS[Q[v]][j+1], TT[SZ(V[v])][j][q]);
            }
          }
        }
        else
        if (t == 0)
        {
          if (!q)
            add(RS[v][j], TT[SZ(V[v])][j][q]);
          if (q)
            add(RS[v][j+1], TT[SZ(V[v])][j][q]);
        }
      }

    // FOR (t,0,6)
    //   cout << v << ' ' << t << ' ' << RS[v][t] << endl;

    // cout << endl;
  }

  FOR (i,0,CNT)
    if (i <= C[0] && (C[0]-i) % k == 0)
      add(res, RS[0][i]);

  return res;
}

int main()
{
  int t;
  cin >> t;
  
  FOR (tt,0,t)
  {
    FOR (i,0,n)
      G[i].clear();

    scanf("%d %d", &n, &k);
    FOR (i,0,n-1)
    {
      int u, v;
      scanf("%d %d", &u, &v);
      -- u;
      -- v;
      G[u].PB(v);
      G[v].PB(u);
    }

    FOR (i,0,n)
    {
      C[i] = 0;
      V[i].clear();

      FOR (j,0,CNT)
      {
        RS[i][j] = 0;
        // FOR (t,0,2)
        //   RL[i][j][t] = 0;
      }
    }

    P.clear();

    dfs(0, -1);

    int res = 0;

    if (k < pow(n, 0.25))
    {
      res = solveSmall();
    }
    else
    {
       res = solveLarge();
    }

    printf("%d\n", res);

  }
  
  
  return 0;
}