C. In Agreement
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an undirected tree with $$$n$$$ vertices. Vertex $$$i$$$ has a positive integer weight $$$a_i$$$.

You may choose any vertex as the root of the tree and any positive integer $$$k$$$.

After rooting the tree, let $$$s_v$$$ denote the sum of the weights of all vertices in the subtree of vertex $$$v$$$, including $$$v$$$ itself.

A choice of the root and $$$k$$$ is valid if all subtree sums have the same remainder modulo $$$k$$$.

Find the maximum possible value of $$$k$$$ among all valid choices.

Input

The first line contains a single integer $$$T$$$ ($$$1 \le T \le 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of vertices.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — the weights of the vertices.

Each of the next $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le n$$$, $$$u \ne v$$$), denoting an edge between vertices $$$u$$$ and $$$v$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print a single integer — the maximum possible value of $$$k$$$.

Example
Input
1
4
1 1 1 1
1 2
1 3
1 4
Output
3
Note

Choose vertex $$$1$$$ as the root and $$$k=3$$$. The subtree sums are $$$4,1,1,1$$$, all of which leave remainder $$$1$$$ modulo $$$3$$$.