#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld double
#define uint unsigned long long
#define endl '\n'
#define ll __int128
#define pii pair<int,int>
#define pa first
#define pb second
#define counts __builtin_popcountll
namespace OOO
{
	char buf[1 << 20], *_now = buf, *_end = buf;
//	#define getchar() (_now == _end && (_end = (_now = buf) + fread(buf, 1, 1 << 20, stdin), _now == _end) ? EOF : *_now++)
    inline void fast_io()
    {
        std::ios::sync_with_stdio(false);
        std::cin.tie(0);
        std::cout.tie(0);
    }
    int fast_pow(int a,int b,int mod)
    {
        int ans=1;
        a%=mod;
        for(;b;b>>=1)
        {
            if(b&1)
            {
                ans=ans*a%mod;
            }
            a=a*a%mod;
        }
        return ans;
    }
    int get_int()
    {
        int x=0;
        bool y=0;
        char c=getchar();
        for(;c<'0'||c>'9';c=getchar())
        {
            if(c=='-')
            {
                y=1;
            }
        }
        for(;c>='0'&&c<='9';c=getchar())
        {
            x=(x<<3)+(x<<1)+c-'0';
        }
        return y?-x:x;
    }
    template<typename T> void out_int(T x)
	{
		if(x==0)
		{
			putchar('0');
			return;
		}
		if(x<0)
		{
			putchar('-');
			x=-x;
		}
		static int num[20],top;
		top=0;
		for(;x;x/=10)
		{
			num[top++]=x%10;
		}
		for(;top;)
		{
			putchar(num[--top]+'0');
		}
	}
    int ni(int a,int mod)
    {
        return fast_pow(a,mod-2,mod);
    }
    int sgn(ld x)
    {
        static const ld eps=1e-12;
        if(fabs(x)-eps<0)
        {
            return 0;
        }
        return x>0?1:-1;
    }
}using namespace OOO;
const int mod=998244353;
int _(int x)
{
	return (x%mod+mod)%mod;
}
int n,k;
vector<vector<int>> road;
void read()
{
	cin>>n>>k;
	road=vector<vector<int>>(n+1);
	for(int w=1,a,b;w<n;w++)
	{
		cin>>a>>b;
		road[a].push_back(b);
		road[b].push_back(a);
	}
}
namespace Solve_big
{
	class node
	{
		public:
			int size,k0_size,k1_size;
			int fa;
			vector<vector<int>> dp;
	};
	vector<node> th;
	void dfs(int w,int fa)
	{
		th[w].fa=fa;
		th[w].size=1;
		th[w].k0_size=th[w].size/k;
		th[w].k1_size=th[w].size/(k+1);
		th[w].dp=vector<vector<int>>(th[w].k0_size+1,vector<int>(th[w].k1_size+1));
		th[w].dp[0][0]=1;
		for(auto to:road[w])
		{
			if(to==th[w].fa)
			{
				continue;
			}
			dfs(to,w);
			th[w].size+=th[to].size;
			
			th[w].k0_size+=th[to].k0_size;
			th[w].k1_size+=th[to].k1_size;
			
			vector<vector<int>> dp(th[w].k0_size+1,vector<int>(th[w].k1_size+1));
			for(int s0=0;s0<=th[w].k0_size;s0++)
			{
				for(int ls0=max(s0-th[to].k0_size,0ll);ls0<=min(th[w].k0_size-th[to].k0_size,s0);ls0++)
				{
					for(int s1=0;s1<=th[w].k1_size;s1++)
					{
						for(int ls1=max(s1-th[to].k1_size,0ll);ls1<=min(th[w].k1_size-th[to].k1_size,s1);ls1++)
						{
							dp[s0][s1]=_(dp[s0][s1]+_(th[w].dp[ls0][ls1]*th[to].dp[s0-ls0][s1-ls1]));
						}
					}
					
				}
			}
			th[w].dp=dp;
			
			th[to].dp.clear();
		}
				
		vector<vector<int>> dp=vector<vector<int>>(th[w].size/k+1,vector<int>(th[w].size/(k+1)+1));
		for(int s0=0;s0<=th[w].k0_size;s0++)
		{
			for(int s1=0;s1<=th[w].k1_size;s1++)
			{
				dp[s0][s1]=_(dp[s0][s1]+th[w].dp[s0][s1]);
				int residue=th[w].size-s0*k-s1*(k+1);
				if(residue>=k)
				{
					dp[s0+1][s1]=_(dp[s0+1][s1]+th[w].dp[s0][s1]);
				}
				if(residue>=k+1)
				{
					dp[s0][s1+1]=_(dp[s0][s1+1]+th[w].dp[s0][s1]);
				}
			}
		}
		th[w].dp=dp;
		
		th[w].k0_size=th[w].size/k;
		th[w].k1_size=th[w].size/(k+1);
	}
	int solve()
	{
		if(n%k>n/k)
		{
			return 0;
		}
		th=vector<node>(n+1);
		dfs(1,0);
		return th[1].dp[n/k-n%k][n%k];
	}
}
namespace Solve_small
{
	class node
	{
		public:
			int size;
			int fa;
			vector<int> dp;
	};
	vector<node> th;
	void dfs(int w,int fa)
	{
		th[w].fa=fa;
		th[w].size=1;
		th[w].dp=vector<int>(min(th[w].size,k+1)+1);
		th[w].dp[1]=1;
		for(auto to:road[w])
		{
			if(to==th[w].fa)
			{
				continue;
			}
			dfs(to,w);
			th[w].size+=th[to].size;
			
			vector<int> dp(min(th[w].size,k+1)+1);
			for(int s=0;s<=min(th[w].size,k+1);s++)
			{
				for(int ls=max(s-min(th[to].size,k+1),0ll);ls<=min(th[w].size-min(th[to].size,k+1),s);ls++)
				{
					dp[s]=_(dp[s]+_(th[w].dp[ls]*th[to].dp[s-ls]));
				}
			}
			th[w].dp=dp;
			
			th[to].dp.clear();
		}
		th[w].dp[0]=_(th[w].dp[0]+(th[w].size>=k?th[w].dp[k]:0)+(th[w].size>=k+1?th[w].dp[k+1]:0));
	}
	int solve()
	{
		th=vector<node>(n+1);
		dfs(1,0);
		return th[1].dp[0];
	}
} 
signed main()
{
	int t;
	cin>>t;
	for(;t--;)
	{
		read();
		cout<<(k*k*k>n*n?Solve_big::solve():Solve_small::solve())<<endl;
	}
}