You are given a tree consisting of vertices. Recall that a tree is an undirected connected acyclic graph.
Now, calculate the number of simple path pairs that each pair of simple paths does not pass through the same vertex. Note that and should only be calculated once. As the answer may be too big, output the answer module .

The simple path is the path that visits each vertex at most once. The path only visits a single vertex is also a path.

输入描述:

The first line contains a single integer  --- the number of test cases.
The first line of each test case contains a single integer  --- the number of vertices.
The next  lines of each test case describe the edges of the tree in form of .  It is guaranteed that given graph is a tree.
It is guaranteed that  over all test cases.

输出描述:

For each test case, output a single integer in a line --- the answer module .

1
3
1 2
1 3

5

 pairs of paths in the sample are: