#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5, INF = 1e7;
int n, K, a[maxn], f[maxn][1005], head[maxn], tot, Gcd[1005][1005], T;
vector<int> vect;
struct node {
	int v, pre;
}e[maxn << 1];
void add(int u, int v) {
	e[++ tot].v = v;
	e[tot].pre = head[u];
	head[u] = tot;
}
int lcm(int x, int y) {
	return x * y / Gcd[x][y];
}
void dfs(int now, int fa) {
	vector<int> vec(1005);
	for(int i = head[now];i;i = e[i].pre) {
		int v = e[i].v;
		if(v == fa) continue;
		dfs(v, now);
		for(int i = 0;i < vect.size();i++) vec[vect[i]] += f[v][i]; 
	}
	for(int id = 0;id < vect.size();id++) {
		int i = vect[id];
		if((a[now] * Gcd[i][a[now]]) % i != 0) {
			f[now][id] = INF;
		}
		else {
			f[now][id] = INF;
			for(int j = 0;j < vect.size();j++) {
				if((vect[j] * a[now]) % i != 0) continue;
				f[now][id] = min(f[now][id], vec[lcm(vect[j], i / Gcd[vect[j]][i])] + 1);
			}
			if(a[now] % i == 0) f[now][id] = min(f[now][id], vec[i]);
		}
	}
}
void solve() {
	vect.clear();
	cin >> n >> K;
	for(int i = 1;i <= n;i++) cin >> a[i];
	for(int i = 1, u, v;i < n;i++) {
		cin >> u >> v;
		add(u, v), add(v, u);
	}
	if(!K) {
		cout << a[1] << '\n';
		tot = 0;
		for(int i = 1;i <= n;i++) head[i] = 0;
		return;
	}
	for(int i = 1;i <= a[1];i++) if(a[1] % i == 0) vect.push_back(i);
	dfs(1, 0);
	vector<int> vec(1005);
	for(int i = head[1];i;i = e[i].pre) {
		int v = e[i].v;
		for(int j = 0;j < vect.size();j++) vec[j] += f[v][j];
	}
	int ans = 0;
	for(int i = 0;i < vect.size();i++) {
		if(vec[i] < K) ans = max(ans, a[1] * vect[i]);
	}
	
	cout << ans << '\n';
	tot = 0;
	for(int i = 1;i <= n;i++) {
		head[i] = 0;
	}
}
int main() {
//	freopen("1.in", "r", stdin);
//	freopen("my.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	for(int i = 1;i <= 1000;i++) for(int j = 1;j <= 1000;j++) Gcd[i][j] = __gcd(i, j);
	cin >> T;
	while(T --) solve();
}

附maker:

#include <bits/stdc++.h>
using namespace std;
int T = 10, n = 10000;
int t[3];
mt19937 rnd(time(0));

namespace Random
{

const auto seed=chrono::steady_clock::now().time_since_epoch().count();
mt19937 mt_rnd(seed);

template<typename IntT>
inline enable_if_t<is_integral<IntT>::value,IntT> randi(const IntT &l,const IntT &r) //[l,r]
{ return uniform_int_distribution<IntT>(l,r)(mt_rnd); }

template<typename FloatT>
inline enable_if_t<is_floating_point<FloatT>::value,FloatT> randf(const FloatT &l,const FloatT &r) //[l,r]
{ return uniform_real_distribution<FloatT>(l,r)(mt_rnd); }

template<typename Iter,typename IntT>
inline enable_if_t<is_integral<IntT>::value> randFilli(Iter first,Iter last,IntT l,IntT r) //[first,last)
{ for(uniform_int_distribution<IntT> rng(l,r);first!=last;*(first++)=rng(mt_rnd)); }

template<typename Iter,typename FloatT>
inline enable_if_t<is_floating_point<FloatT>::value> randFillf(Iter first,Iter last,FloatT l,FloatT r) //[first,last)
{ for(uniform_real_distribution<FloatT> rng(l,r);first!=last;*(first++)=rng(mt_rnd)); }

template<typename FloatT,typename ResT=bool>
inline const ResT &probability(FloatT p,const ResT &a=true,const ResT &b=false)
{ return bernoulli_distribution(p)(mt_rnd)?a:b; }

template<typename Iter>
inline Iter choose(Iter first,Iter last) //[first,last)
{ return first+mt_rnd()%distance(first,last); }

template<typename Iter>
inline void shuffle(Iter first,Iter last) //[first,last)
{ for(;first!=last;++first)swap(*first,*(first+mt_rnd()%distance(first,last))); }

template<typename IntT>
inline enable_if_t<is_integral<IntT>::value,pair<IntT,IntT>> subinterval(IntT l,IntT r)
{
    IntT resl=randi(l-1,r),resr=randi(l,r);
    if(resl<l) return make_pair(resr,resr);
    return minmax(resl,resr);
}

template<typename FloatT>
inline enable_if_t<is_floating_point<FloatT>::value,pair<FloatT,FloatT>> subinterval(FloatT l,FloatT r)
{
    FloatT resl=randf(l,r),resr=randf(l,r);
    return minmax(l,r);
}

template<typename InIter,typename OutIter>
inline OutIter sample(InIter first,InIter last,int n,OutIter out) //[first,last)
{
    auto m=distance(first,last);
    for((m<n&&(n=m));n;++first,m--)
        if(mt_rnd()%m<n) *out++=*first,n--;
    return out;
}

template<typename IntT,typename OutIter>
inline enable_if_t<is_integral<IntT>::value,OutIter> rangeSample(IntT l,IntT r,int n,OutIter out) //[l,r]
{
    unordered_set<IntT> s;
    IntT m=r-l+1,lim=m*0.6,x;
    for(n=min((IntT)n,m);n && m>lim;n--,m--)
    {
        while(s.find(x=randi(l,r))!=s.end());
        *out++=x,s.insert(x);
    }
    if(!n) return out;
    for(IntT i=l;i<=r;i++)
    {
        if(s.find(i)!=s.end()) continue;
        if(mt_rnd()%(m--)<n) *out++=i,n--;
    }
    return out;
}

vector<pair<int,int>> randTree(int n)
{
    vector<pair<int,int>> res;
    if(n<2) return res;
    vector<int> prf(n-2),deg(n+1,1);
    int p=0,u;
    randFilli(prf.begin(),prf.end(),1,n);
    for(auto &i: prf) deg[i]++;
    while(deg[u=++p]!=1);
    for(auto &v: prf)
    {
        res.emplace_back(u,v);
        if((--deg[v])==1 && v<p) u=v;
        else while(deg[u=++p]!=1);
    }
    res.emplace_back(n,u);
    return res;
}

vector<pair<int,int>> randTree(int n,int span)
{
    vector<pair<int,int>> res;
    if(n<2) return res;
    vector<int> fa(n+1),p(n);
    iota(p.begin(),p.end(),1),shuffle(p.begin(),p.end());
    for(int i=2;i<=n;i++)
    {
        int FloatT=abs(span),x;
        if(span>0) for(x=0;FloatT--;x=max(x,randi(1,i-1)));
        else if(span<0) for(x=n+1;FloatT--;x=min(x,randi(1,i-1)));
        else x=randi(1,i-1);
        fa[i]=x;
    }
    for(int i=2;i<=n;i++) res.emplace_back(p[i-1],p[fa[i]-1]);
    shuffle(res.begin(),res.end());
    return res;
}

} // namespace Random

int main() {
	freopen("1.in", "w", stdout);
	cout << T << '\n';
	for(int i = 1;i <= T;i++) {
		cout << n << " ";
		cout << rnd() % (n + 1) << "\n";
		int g = rnd() % 100 + 1;
		for(int j = 1;j <= n;j++) cout << (rnd() % (1000 / g) + 1) * g << ' ';
		cout << '\n';
		auto q = Random::randTree(n);
		for (auto p : q) {
			cout << p.first << ' ' << p.second << '\n';
		}
	}
}