David Mills and William Somerset have teamed up again to catch a criminal. This criminal is a bit different from others, he challenges the detectives by leaving a puzzle at the crime scene which is the clue to his next crime. Both the detectives work hard to crack the puzzle, but the criminal is always one step ahead. For his 7^th and last crime, he left a problem for the detectives. David wants your help for this one to catch the criminal.

The criminal gave you a tree having n nodes with 1 as the root. Each node is numbered from 1 to n. Every node has a value represented by the array A.

You are given another array B. You have to convert the node values from A to B by performing the minimum number of operations. In one operation you can select any node i and add or subtract any value. And the same value will get added to or subtracted from the special node in the subtree of the node i.

Special node q in the subtree of p is defined as node such that:

(Number of set bits in p) mod 2 = (Number of set bits in q) mod 2

You have to tell the minimum operations to convert node values from A to B and the sum of values added or subtracted in these operations.

Constraints

1 ≤ t ≤ 11

1 ≤ n ≤ 100000

1 ≤ A[i] ≤ 100000

1 ≤ B[i] ≤ 100000

Input

1. The first line of the input contains a single integer t denoting the number of test cases. The description of t test cases follows.
2. The first line of each test case contains a single integer n denoting the number of nodes.
3. Each of the next  n - 1 lines contains two integers u_i and v_i (1 ≤ u_i, v_i ≤ n ; u_i ≠ v_i) meaning there is an edge between nodes u_i and v_i.
4. Next line has n space-separated integers A₁, A₂, A₃ , ... A_n denoting the initial value of nodes.
5. Next line has n space-separated integers B₁, B₂, B₃ , ... B_n denoting the final values of nodes. 

Output

Output the minimum number of operations required and the sum of values added or subtracted in these operations.

Example

Input:
1
8
1 3
3 2
3 7
6 2
4 1
8 4
4 5
9 3 5 6 2 3 8 10
9 3 3 5 2 1 8 10
Output:
3 -2

Explanation

You can select node 3 with value 5 and subtract 2, it will also get subtracted from the special node 6 in its subtree.

Values after 1^st operation: 9 3 3 6 2 1 8 10

Now select node 4 with value 6 and subtract 1, it will also get subtracted from the special node 8 in its subtree.

Values after 2^nd operation: 9 3 3 5 2 1 8 9

Now select node 8 and add 1. There is no special node in its subtree.

Values after 3^rd operation: 9 3 3 5 2 1 8 10

Sum of values added/subtracted = -2-1+1 = -2