Kanade is designing a mini-game. It's a puzzle game that orders players to get out of a maze. Players should also collect as many kinds of elements as they can to gain a better score.
For the easy mode, the maze can be described as a tree. There are n crossings and n−1 undirected passages which make the n crossings connected. The n crossings is numbered with integers from 1 to n. Exactly one element is placed on each crossing. The kind of element placed at crossing i is denoted by an integer ci in the range [1,n].
To evaluate the maze's difficulty, Kanade wants to know how many kinds of elements appear on p(u,v) for every two integers u,v∈[1,n]. p(u,v) indicates the simple path from crossing u to crossing v in the maze.
Input
The first line of input contains one integer T (1≤T≤10), indicating the number of test cases.
For each test case, the first line contains one integer n (2≤n≤2000), indicating the number of crossings in the maze.
The second line contains n−1 integers p2,p3,…,pn (pi<i), indicating that the i-th crossing is connected with the pi-th crossing by a passage.
The third line contains n integers c1,c2,…,cn (1≤ci≤n), indicating that the kind of element placed at crossing i is ci.
It is promised that for all test cases, ∑n≤5000.
Output
For each test case, output n lines. Each line contains two integers. Let ai,j be the number of kinds of elements appear on p(i,j). Let
f(i,x)=∑nj=1 ai,jxj−1
Then for the i-th line, output f(i,19560929)mod(109+7) and f(i,19560929)mod(109+9), space separated.