package main

import (
	"io"
	"math/bits"
	"os"
	"strconv"
)

type Segment struct {
	l, r int
	len  int
	dir  int
	mask uint32
}

func lowerBound32(a []int32, x int) int {
	v := int32(x)
	l, r := 0, len(a)
	for l < r {
		m := (l + r) >> 1
		if a[m] < v {
			l = m + 1
		} else {
			r = m
		}
	}
	return l
}

func upperBound32(a []int32, x int) int {
	v := int32(x)
	l, r := 0, len(a)
	for l < r {
		m := (l + r) >> 1
		if a[m] <= v {
			l = m + 1
		} else {
			r = m
		}
	}
	return l
}

func rangeOr(seg []uint32, size, l, r int) uint32 {
	l += size
	r += size
	var res uint32
	for l <= r {
		if l&1 == 1 {
			res |= seg[l]
			l++
		}
		if r&1 == 0 {
			res |= seg[r]
			r--
		}
		l >>= 1
		r >>= 1
	}
	return res
}

func lca(u, v int, head, parent, depth []int) int {
	for head[u] != head[v] {
		if depth[head[u]] > depth[head[v]] {
			u = parent[head[u]]
		} else {
			v = parent[head[v]]
		}
	}
	if depth[u] < depth[v] {
		return u
	}
	return v
}

func main() {
	data, _ := io.ReadAll(os.Stdin)
	idx := 0
	nextInt := func() int {
		for idx < len(data) && (data[idx] < '0' || data[idx] > '9') {
			idx++
		}
		val := 0
		for idx < len(data) && data[idx] >= '0' && data[idx] <= '9' {
			val = val*10 + int(data[idx]-'0')
			idx++
		}
		return val
	}

	t := nextInt()
	out := make([]byte, 0, 1<<20)

	for ; t > 0; t-- {
		n := nextInt()
		a := make([]uint32, n+1)
		for i := 1; i <= n; i++ {
			a[i] = uint32(nextInt())
		}

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

		parent := make([]int, n+1)
		depth := make([]int, n+1)
		order := make([]int, 0, n)
		stack := make([]int, 1, n)
		stack[0] = 1

		for len(stack) > 0 {
			v := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			order = append(order, v)
			for _, to := range adj[v] {
				if to == parent[v] {
					continue
				}
				parent[to] = v
				depth[to] = depth[v] + 1
				stack = append(stack, to)
			}
		}

		sz := make([]int, n+1)
		heavy := make([]int, n+1)
		for i := n - 1; i >= 0; i-- {
			v := order[i]
			s := 1
			h := 0
			hs := 0
			for _, to := range adj[v] {
				if to == parent[v] {
					continue
				}
				s += sz[to]
				if sz[to] > hs {
					hs = sz[to]
					h = to
				}
			}
			sz[v] = s
			heavy[v] = h
		}

		head := make([]int, n+1)
		pos := make([]int, n+1)
		inv := make([]int, n)
		cur := 0
		for v := 1; v <= n; v++ {
			if parent[v] == 0 || heavy[parent[v]] != v {
				for u := v; u != 0; u = heavy[u] {
					head[u] = v
					pos[u] = cur
					inv[cur] = u
					cur++
				}
			}
		}

		base := make([]uint32, n)
		var cntBit [30]int
		for p := 0; p < n; p++ {
			val := a[inv[p]]
			base[p] = val
			for m := val; m != 0; m &= m - 1 {
				cntBit[bits.TrailingZeros32(m)]++
			}
		}

		var bitPos [30][]int32
		for b := 0; b < 30; b++ {
			bitPos[b] = make([]int32, 0, cntBit[b])
		}
		for p := 0; p < n; p++ {
			val := base[p]
			for m := val; m != 0; m &= m - 1 {
				b := bits.TrailingZeros32(m)
				bitPos[b] = append(bitPos[b], int32(p))
			}
		}

		segSize := 1
		for segSize < n {
			segSize <<= 1
		}
		seg := make([]uint32, segSize<<1)
		copy(seg[segSize:segSize+n], base)
		for i := segSize - 1; i > 0; i-- {
			seg[i] = seg[i<<1] | seg[i<<1|1]
		}

		q := nextInt()
		for ; q > 0; q-- {
			x := nextInt()
			y := nextInt()
			l := lca(x, y, head, parent, depth)

			var segs [64]Segment
			slen := 0
			var temp [64]Segment
			tlen := 0

			u := x
			for head[u] != head[l] {
				L := pos[head[u]]
				R := pos[u]
				segs[slen] = Segment{l: L, r: R, len: R - L + 1, dir: 0}
				slen++
				u = parent[head[u]]
			}
			L := pos[l]
			R := pos[u]
			segs[slen] = Segment{l: L, r: R, len: R - L + 1, dir: 0}
			slen++

			v := y
			for head[v] != head[l] {
				L = pos[head[v]]
				R = pos[v]
				temp[tlen] = Segment{l: L, r: R, len: R - L + 1, dir: 1}
				tlen++
				v = parent[head[v]]
			}
			if pos[l]+1 <= pos[v] {
				L = pos[l] + 1
				R = pos[v]
				temp[tlen] = Segment{l: L, r: R, len: R - L + 1, dir: 1}
				tlen++
			}
			for i := tlen - 1; i >= 0; i-- {
				segs[slen] = temp[i]
				slen++
			}

			var pathMask uint32
			for i := 0; i < slen; i++ {
				m := rangeOr(seg, segSize, segs[i].l, segs[i].r)
				segs[i].mask = m
				pathMask |= m
			}

			var firstX, firstY [30]int
			for i := 0; i < 30; i++ {
				firstX[i] = -1
				firstY[i] = -1
			}

			missing := pathMask
			off := 0
			for i := 0; i < slen && missing != 0; i++ {
				sg := segs[i]
				hit := missing & sg.mask
				if hit != 0 {
					for m := hit; m != 0; m &= m - 1 {
						b := bits.TrailingZeros32(m)
						arr := bitPos[b]
						if sg.dir == 1 {
							p := int(arr[lowerBound32(arr, sg.l)])
							firstX[b] = off + p - sg.l
						} else {
							p := int(arr[upperBound32(arr, sg.r)-1])
							firstX[b] = off + sg.r - p
						}
					}
					missing &^= hit
				}
				off += sg.len
			}

			missing = pathMask
			off = 0
			for i := slen - 1; i >= 0 && missing != 0; i-- {
				sg := segs[i]
				hit := missing & sg.mask
				if hit != 0 {
					dir := sg.dir ^ 1
					for m := hit; m != 0; m &= m - 1 {
						b := bits.TrailingZeros32(m)
						arr := bitPos[b]
						if dir == 1 {
							p := int(arr[lowerBound32(arr, sg.l)])
							firstY[b] = off + p - sg.l
						} else {
							p := int(arr[upperBound32(arr, sg.r)-1])
							firstY[b] = off + sg.r - p
						}
					}
					missing &^= hit
				}
				off += sg.len
			}

			dist := depth[x] + depth[y] - 2*depth[l]

			var blist [30]int
			bc := 0
			for m := pathMask; m != 0; m &= m - 1 {
				blist[bc] = bits.TrailingZeros32(m)
				bc++
			}

			var cand [60]int
			cc := 0
			for i := 0; i < bc; i++ {
				b := blist[i]
				cand[cc] = firstX[b]
				cc++
				cand[cc] = dist - firstY[b]
				cc++
			}

			best := 0
			for i := 0; i < cc; i++ {
				p := cand[i]
				cnt := 0
				for j := 0; j < bc; j++ {
					b := blist[j]
					if firstX[b] <= p && p <= dist-firstY[b] {
						cnt++
					}
				}
				if cnt > best {
					best = cnt
				}
			}

			ans := bc + best
			out = strconv.AppendInt(out, int64(ans), 10)
			out = append(out, '\n')
		}
	}

	_, _ = os.Stdout.Write(out)
}