Chiaki has a tree with n vertices. There might be a token colored white or black on each vertex of the tree, and there are exactly w white tokens and exactly b black tokens. Also, for each pair of vertices with the same color of tokens, there must have been a path between them such that every vertex on the path contains a token of the same color.

Chiaki would like to perform the following operations:

• Choose a vertex u with a token.
• Choose a path such that , all vertices contain a token of the same color, and there's no token in .
• Move the token in to . Now there's no token in and contains a token.

For two initial configurations of tokens S and T, if Chiaki could perform the above operations several times to make S become T, S and T are considered equivalent.

Let f(w, b) be the number of equivalence classes (an equivalence class is a maximal set of configurations where each two of them are equivalent; all equivalence classes partition the set of all configurations), Chiaki would like to know the value of

There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. 

For each test case, the first line contains an integer n () -- the number of vertices in the tree. The second line contains n-1 integers  (), where  means there is an edge between vertex i and vertex .

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

For each test case, output an integer denoting the value of 

2
5
1 2 3 3
10
1 2 3 4 3 6 3 8 2

71
989

For the first sample, the value of f(w,b) for each w and b: f(1,1)=1, f(1,2)=2, f(1,3)=3, f(1,4)=3, f(2,1)=2, f(2,2)=2, f(2,3)=1, f(3,1)=3, f(3,2)=1, and f(4,1)=3.