There is a rooted tree with vertices and the root vertex is . In each vertex, there is a monster. The hit points of the monster in the -th vertex is .

Kotori would like to kill all the monsters. The monster in the -th vertex could be killed if the monster in the direct parent of the -th vertex has been killed. The power needed to kill the -th monster is the sum of and the hit points of all other living monsters who lives in a vertex whose direct parent is . Formally, the power equals to

In addition, Kotori can use some magic spells. If she uses one magic spell, she can kill any monster using power without any restriction. That is, she can choose a monster even if the monster in the direct parent is alive.

For each , Kotori would like to know, respectively, the minimum total power needed to kill all the monsters if she can use magic spells.

输入描述:

There are multiple test cases. The first line of input contains an integer  indicating the number of test cases. For each test case:

The first line contains an integer  (), indicating the number of vertices.

The second line contains  integers  (), where  means the direct parent of vertex .

The third line contains  integers  () indicating the hit points of each monster.

It's guaranteed that the sum of  of all test cases will not exceed .

输出描述:

For each test case output one line containing  integers  separated by a space, where  indicates the minimum total power needed to kill all the monsters if Kotori can use  magic spells.

Please, DO NOT output extra spaces at the end of each line, otherwise your answer may be considered incorrect!

3
5
1 2 3 4
1 2 3 4 5
9
1 2 3 4 3 4 6 6
8 4 9 4 4 5 2 4 1
12
1 2 2 4 5 3 4 3 8 10 11
9 1 3 5 10 10 7 3 7 9 4 9

29 16 9 4 1 0
74 47 35 25 15 11 7 3 1 0
145 115 93 73 55 42 32 22 14 8 4 1 0