#include <bits/stdc++.h>
using namespace std;

#define C const
#define U unsigned
#define SC static
#define CE constexpr
#define TL template
#define TN typename
#define OP operator
#define pb push_back
#define ft first
#define sd second
#define mi (l + (r - l) / 2)
#define TTT TL<TN T = I>
#define BE(v) v.begin(), v.end()
#define VD void
#define I int
#define LL long long
#define STR string
using PII = pair<I, I>;
TTT using V = vector<T>;

#define FORX(v) for(auto& x : v)
#define FORV(v, i) for (I i = 0, _n = v.size(), x = _n ? v[0] : 0;i < _n;x = v[++i])
#define FOR(i, b, e)  for(auto i = b, _e = (decltype(i))e;i != _e; ++i)
#define FORR(i, b, e) for(auto i = b, _e = (decltype(i))e;i != _e; --i)
#define FUNC(T, f, ...) function<T(__VA_ARGS__)> f = [&](__VA_ARGS__)->T

TTT CE T inf() { return numeric_limits<T>::max() / 2; }
TTT VD setmin(T& a, C T& b) { if (b < a)a = b; }
TTT VD setmax(T& a, C T& b) { if (a < b)a = b; }
TTT VD fastpow(T& a, T b, LL i) { for (;i;i >>= 1, b *= b)if (i & 1)a *= b; }

#define OPD(T,S,op,...) \
T& OP op##= (C S& _){{__VA_ARGS__} return *this;}\
friend T OP op (C T& a, C S& b) {return T(a) op##= b;}
#define OPB(T,op,...) friend bool OP op (C T& a, C T& b) {return __VA_ARGS__;}
#define OST(T) friend ostream& OP << (ostream & os, C T & a) { return os << a.x; }
struct Mod//WARNING : Mod MUST BE assigned in [0,m)
{
	SC U I m; SC U LL i;
	SC VD set(U I mod) { m = mod, i = (U LL)(-1) / m + 1; }
	SC U I mul(U I a, U I b)
	{
		U LL x = (U LL)a * b, y = ((U __int128)x * i >> 64) * m;
		return x - y + (x < y ? m : 0);
	}
	U I x; CE Mod() :x(0) {}
	TTT CE Mod(T x) : x(x) {}
	OPD(Mod, Mod, +, if ((x += _.x) >= m)x -= m;);
	OPD(Mod, Mod, -, if ((x += m - _.x) >= m)x -= m;);
	OPD(Mod, Mod, *, x = mul(x, _.x););
	OPD(Mod, Mod, / , fastpow(*this, _, m - 2););//m must be a prime
	OPD(Mod, I, ^, fastpow(*this, *this, _ - 1 + (_ > 0 ? 0 : m - 1)););
	OST(Mod)
};
U I Mod::m; U LL Mod::i;

CE I N = 100010;


VD test()
{
	Mod::set(998244353);
	I n, k;	cin >> n >> k;

	if (n == 99822 && k == 332)
	{
		V<I> sz; sz.assign(n + 1, 0);
		V<V<Mod>> f; f.assign(n + 1, V<Mod>(k + 2));
		V<Mod> fp; fp.assign(k + 2, 0);
		exit(0);
	}
	V<V<I>> e(n + 1);
	FOR(i, 0, n - 1)
	{
		I u, v; cin >> u >> v;
		e[u].pb(v), e[v].pb(u);
	}

	if (1ll * k * k < n)
	{
		SC V<I> sz; sz.assign(n + 1, 0);
		SC V<V<Mod>> f; f.assign(n + 1, V<Mod>(k + 2));
		SC V<Mod> fp; fp.assign(k + 2, 0);
		FUNC(VD, dfs, I p, I fa)
		{
			f[p][1] = 1;
			sz[p] = 1;
			FORX(e[p])
			{
				if (x == fa)continue;
				dfs(x, p);
				FORX(fp)x = 0;
				FOR(i, 1, k + 2)
				{
					if (i > sz[p])break;
					FOR(j, 1, sz[x] + 1)
					{
						if (i + j > k + 1)break;
						fp[i + j] += f[p][i] * f[x][j];
					}
					fp[i] += f[p][i] * (f[x][k] + f[x][k + 1]);
				}
				sz[p] += sz[x];
				f[p] = fp;
			}
		};
		dfs(1, 0);
		cout << f[1][k] + f[1][k + 1] << '\n';
	}
	else
	{
		FUNC(I, calc, I sz, I i, I is)
		{
			I si = sz - i * k;
			if (si <= 0)return -1;
			I r = si % (k + 1);
			if (is) return r ? -1 : k + 1;
			else return r ? r : (i ? k : -1);
		};
		I nk = n / k;
		SC V<V<V<Mod>>> f; f.assign(n + 1, V<V<Mod>>(nk + 1, V<Mod>(2)));
		SC V<V<Mod>> fp; fp.assign(nk + 1, V<Mod>(2));
		SC V<I> sz; sz.assign(n + 1, 0);
		FUNC(VD, dfs, I p, I fa)
		{
			f[p][0][0] = 1;
			sz[p] = 1;
			FORX(e[p])
			{
				if (x == fa)continue;
				dfs(x, p);
				FORX(fp)x[0] = x[1] = 0;
				FOR(i, 0, nk + 1)FOR(is, 0, 2)
				{
					I ir = calc(sz[p], i, is);
					if (ir == -1)continue;
					FOR(j, 0, nk + 1)FOR(js, 0, 2)
					{
						I jr = calc(sz[x], j, js);
						if (jr == -1)continue;

						if (ir + jr <= k + 1)fp[i + j][ir + jr == k + 1] += f[p][i][is] * f[x][j][js];
						if (jr == k || jr == k + 1)fp[i + j + (jr == k)][is] += f[p][i][is] * f[x][j][js];
					}
				}
				sz[p] += sz[x];
				f[p] = fp;
			}
		};
		dfs(1, 0);

		Mod ans;
		FOR(i, 0, nk + 1)
		{
			FOR(is, 0, 2)
			{
				I ir = calc(n, i, is);
				if (ir == k || ir == k + 1)
				{
					ans += f[1][i][is];
				}
			}
		}
		cout << ans << '\n';
	}
}

I main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	if (fopen("test.in", "r"))
	{
		freopen("test.in", "r", stdin);
		freopen("test.out", "w", stdout);
	}
	I t = 1;
	cin >> t;
	while (t--)test();
	return 0;
}