G. Modular Tree
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Vihaan has a rooted tree$$$^{\text{∗}}$$$ with $$$n$$$ nodes. The tree is rooted at node $$$1$$$.

Each node $$$i$$$ has an initial value $$$a_i$$$ and a modulus $$$b_i$$$. Let $$$x_i$$$ denote the current value of node $$$i$$$. Initially, $$$x_i=a_i$$$.

Vihaan may perform the following operation any number of times:

  • Choose a node $$$u$$$. Let $$$s$$$ be the sum of the current values of all direct children of $$$u$$$, then replace $$$x_u$$$ with $$$(x_u+s)\bmod b_u$$$.

After performing any number of operations, Vihaan wants to maximize the sum of the values of all nodes.

Determine the maximum possible sum.

$$$^{\text{∗}}$$$A tree is an undirected connected graph in which there are no cycles.

Input

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

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of nodes in the tree.

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$0 \le a_i \lt b_i$$$) — the initial values of the nodes.

The third line contains $$$n$$$ integers $$$b_1,b_2,\ldots,b_n$$$ ($$$1 \le b_i \le 10^9$$$) — the moduli of the nodes.

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

It is guaranteed that the given edges form a tree.

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 one integer — the maximum possible sum of the values of all nodes after performing any number of operations.

Example
Input
8
1
3
7
2
0 3
5 4
1 2
3
0 2 3
7 3 4
1 2
2 3
3
0 0 1
5 2 2
1 2
2 3
4
1 2 3 4
10 3 4 5
1 2
1 3
1 4
3
0 1 3
10 2 4
1 2
1 3
5
0 0 1 2 3
12 6 9 3 4
1 2
1 3
2 4
3 5
4
0 999999999 999999999 999999999
1000000000 1000000000 1000000000 1000000000
1 2
1 3
1 4
Output
3
7
11
6
18
12
27
3999999996
Note

In the first test case, node $$$1$$$ has no children, so performing an operation on it does not change its value. Thus, the maximum possible sum is $$$3$$$.

In the third test case, Vihaan can perform the operation on node $$$1$$$ three times:

  1. $$$[0,2,3] \to [2,2,3]$$$.
  2. $$$[2,2,3] \to [4,2,3]$$$.
  3. $$$[4,2,3] \to [6,2,3]$$$.
The resulting sum is $$$6+2+3=11$$$. It can be shown that no sequence of operations can obtain a larger sum.

In the fourth test case, Vihaan can perform the following operations:

  1. Perform the operation on node $$$2$$$: $$$$$$[0,0,1] \to [0,1,1].$$$$$$
  2. Perform the operation on node $$$1$$$ four times: $$$$$$[0,1,1] \to [1,1,1] \to [2,1,1] \to [3,1,1] \to [4,1,1].$$$$$$
The resulting sum is $$$4+1+1=6$$$. It can be shown that no sequence of operations can obtain a larger sum.