DSUBTREE - Distinct Subtrees

Given an unrooted tree, the subtree is defined as a connected component of the given tree. Two subtrees are considered the same if there exists a map from nodes of one tree to another so that the edges of both trees are corresponding the same pair of nodes after mapping.

Your task is to find out how many distinct subtrees for a given unrooted tree.

Input

The input consists of multiple test cases. The first line of input contains an integer denoting the number of test cases.

For each test case, the first line contains one integer n denoting the number of nodes of the given tree. (1 <= n <= 15)

Then n-1 lines follow, each line contains two integers denoting an edge of the tree. The index of the node counts from 1.

Output

For each test case, output the number of distinct subtrees for the given tree.

Example

Input:
2
3
1 2
1 3
9
9 4
4 3
1 3
7 4
1 6
5 7
2 4
6 8

Output:
Case #1: 3
Case #2: 21

Added by:Fudan University Problem Setters
Date:2011-09-08
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Fudan University Local Contest #3, by g201513

hide comments
2022-07-19 20:26:11 David
First Java solution!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.