It is after years that Dystopian Institute of Technology has got funds for upgrading their computers. However, the people in charge of the upgrade have decided to make this a chance to fill their own pockets rather.

There are N computers in the DIT network, numbered 0 to N-1. Computer 0 is the main server which connects the network to the outer world. Some pairs of the computers are directly connected in the network. For other pair of computers to communicate with each other, they have to do it via some other computer. For example, if there are only 3 computers in the network and the only direct connections are 0-1 and 0-2, then 1 communicates with 2 using 0 as intermediate. There is no limit on the number of intermediate computers to be used for communication between a pair. Now, since the DIT network was built on the principle of minimum expenditure, the N computers have been made pairwise connected by using the minimum number of direct connections - ie, N-1.

The upgrade contractor has decided to not do the work properly but pocket the entire funds instead. However, to show that he has done something, he will rearrange the computers. For example he could move the computer number 3 to where 2 was earlier, 2 to 1, 1 to 3, 4 to 5 and 5 to 4. The computer number 0 is special and cannot be moved. Direct connections between computers depend on the locations though. Hence if there was a direct connection earlier between 3 and 5, it will now be between 1 and 4 (since they have been placed at the locations 3 and 5 were at earlier). However, he has noticed something strange : the new direct connection between computers i and j works if and only if there was a direct connection between i and j earlier. Hence he wants to rearrange the computers in such a way that the pairs of computers which are connected directly now are the same pairs which were connected earlier.

Given the computer network, count the number of ways the computers can be rearranged satisfying the conditions.

Input

The first line of the input contains T, the number of test cases (T ≤ 10). Following this are the descriptions of the test cases. Each description starts with a line containing the integer N, the number of computers in the network (1 ≤ N ≤ 10000). This is followed by N-1 lines, each containing a pair of integers i and j, denoting that computer i is directly connected to computer j. It is assured that these N-1 direct connections will make every pair of computers connected (via intermediates if needed).

Output

For each test case, output the number of rearrangements of the computers. A rearrangement (p₀,p₁,p₂...p_N-1) of (0,1,2...N-1) is valid if the following conditions are satisfied:

• p₀=0
• If there is a direct connection between i and j, there should also be a direct connection between p_i and p_j

Notice that (0,1,2...N-1) is considered a valid rearrangement of itself. Also, since the answer could be very big, output it modulo 1000000007

Example

Input:
1
6
0 1
0 2
0 3
3 4
3 5

Output:
4