package main

import (
	"bufio"
	"fmt"
	"os"
)

func gcd(a, b int) int {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

func readInt(r *bufio.Reader) int {
	var n int
	var c byte
	var err error
	for {
		c, err = r.ReadByte()
		if err != nil {
			return n
		}
		if c >= '0' && c <= '9' {
			n = int(c - '0')
			break
		}
	}
	for {
		c, err = r.ReadByte()
		if err != nil || c < '0' || c > '9' {
			break
		}
		n = n*10 + int(c-'0')
	}
	return n
}

func main() {
	r := bufio.NewReader(os.Stdin)
	w := bufio.NewWriter(os.Stdout)
	defer w.Flush()

	t := readInt(r)
	for tc := 0; tc < t; tc++ {
		n := readInt(r)
		k := readInt(r)

		a := make([]int, n+1)
		for i := 1; i <= n; i++ {
			a[i] = readInt(r)
		}

		adj := make([][]int, n+1)
		for i := 0; i < n-1; i++ {
			u := readInt(r)
			v := readInt(r)
			adj[u] = append(adj[u], v)
			adj[v] = append(adj[v], u)
		}

		a1 := a[1]
		D := []int{}
		for i := 1; i <= a1; i++ {
			if a1%i == 0 {
				D = append(D, i)
			}
		}
		numDivs := len(D)
		idx := make([]int, a1+1)
		for i, d := range D {
			idx[d] = i
		}

		gcdMemo := make([][]int, numDivs)
		for i := 0; i < numDivs; i++ {
			gcdMemo[i] = make([]int, numDivs)
			for j := 0; j < numDivs; j++ {
				gcdMemo[i][j] = idx[gcd(D[i], D[j])]
			}
		}

		opMemo := make([]int, numDivs)
		for i := 0; i < numDivs; i++ {
			opMemo[i] = idx[gcd(D[i]*D[i], a1)]
		}

		order := make([]int, 0, n)
		parent := make([]int, n+1)
		queue := []int{1}
		for len(queue) > 0 {
			u := queue[0]
			queue = queue[1:]
			order = append(order, u)
			for _, v := range adj[u] {
				if v != parent[u] {
					parent[v] = u
					queue = append(queue, v)
				}
			}
		}

		dp := make([][]int, n+1)

		for i := n - 1; i >= 0; i-- {
			u := order[i]
			curr := make([]int, numDivs)
			for j := 0; j < numDivs; j++ {
				curr[j] = 1e9
			}
			g0 := gcd(a[u], a1)
			curr[idx[g0]] = 0

			for _, v := range adj[u] {
				if v == parent[u] {
					continue
				}
				nextCurr := make([]int, numDivs)
				for j := 0; j < numDivs; j++ {
					nextCurr[j] = 1e9
				}
				for j := 0; j < numDivs; j++ {
					cj := curr[j]
					if cj == 1e9 {
						continue
					}
					for l := 0; l < numDivs; l++ {
						dv := dp[v][l]
						if dv == 1e9 {
							continue
						}
						cost := cj + dv
						gNew := gcdMemo[j][l]
						if cost < nextCurr[gNew] {
							nextCurr[gNew] = cost
						}
					}
				}
				curr = nextCurr
			}

			if u == 1 {
				dp[1] = curr
			} else {
				dpu := make([]int, numDivs)
				for j := 0; j < numDivs; j++ {
					dpu[j] = curr[j]
				}
				for j := 0; j < numDivs; j++ {
					if curr[j] == 1e9 {
						continue
					}
					idxOp := opMemo[j]
					cost := curr[j] + 1
					if cost < dpu[idxOp] {
						dpu[idxOp] = cost
					}
				}
				dp[u] = dpu
			}
		}

		maxVal := a1
		for i := 0; i < numDivs; i++ {
			if dp[1][i] <= k-1 {
				val := a1 * D[i]
				if val > maxVal {
					maxVal = val
				}
			}
		}

		fmt.Fprintln(w, maxVal)
	}
}