There are n people numbered from 1 to n. Each people have a unique message. Some pairs of people can send messages directly to each other, and this relationship forms a structure of a tree. In one turn, exactly one person sends all messages s/he currently has to another person. What is the minimum number of turns needed so that everyone has all the messages?
This is not your task. Your task is: count the number of ways that minimizes the number of turns. Two ways are different if there exists some k such that in the k-th turn, the sender or receiver is different in the two ways.

First line, number of test cases, T.
Following are T test cases.
For each test case, the first line is number of people, n. Following are n-1 lines. Each line contains two numbers.

Sum of all n <= 1000000.

T lines, each line is answer to the corresponding test case. Since the answers may be very large, you should output them modulo 10⁹+7.

2
2
1 2
3
1 2
2 3

2
6

2013 Multi-University Training Contest 6