提示: 欢迎访问OurACM平台。
Problem 2142 Center of a Tree

Accept: 41    Submit: 183
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Given a tree T with N vertices, your task is calculating the number of the connected sub-tree of T, which has the same center as T.

Given a graph, the eccentricity of a vertex v is defined as the greatest distance from v to any other vertex. A center of a graph is a vertex with minimal eccentricity. A graph can have an arbitrary number of centers. However, Jordan (1869) has proved that for trees, there are only two possibilities:

1. The tree has precisely one center (centered trees).

2. The tree has precisely two centers (bicentered trees). In this case, the two centers are adjacent.

from wikipedia

Note that in case 2, we just consider that T has two centers, you should only count the sub-tree which has the two same centers as T.

Input

The first line of the date is an integer T, which is the number of the text cases.

Then T cases follow each case starts of a number N described above.

Then N-1 lines follow, each line contains two integers x and y, which means that there is a edge between x and y in tree T, you can assume that the index of T is from 1 to N.

1 <= T <= 100, 1 <= N <=1000.

Output

For each case, output the case number first, then output the number of the connected sub-tree which has the same center as T.

Give your answer modulo 10086.

Sample Input

5 1 2 1 2 3 1 2 1 3 4 1 2 1 3 1 4 5 1 2 1 3 1 4 4 5

Sample Output

Case 1: 1 Case 2: 1 Case 3: 2 Case 4: 5 Case 5: 4

Submit  Back  Status  Discuss