Given a graph, we define "proper coloring" as coloring of the graph nodes in such way that no two adjacent nodes have the same color. If we map each color to a positive integer, we can calculate the sum of all colors assigned to the graph.

In this problem you will be given a tree (connected graph with no simple loops). Can you determine what the minimum color sum can be achieved when the tree is properly colored? (Image to the right shows a proper coloring of the second example tree with sum=11)

Input

The input file consists of several test cases. Each test case starts with n (1 ≤ n ≤ 10000), the number of nodes in the tree. Next n lines will be of the form "u: v1 v2 ... vk" where u is the root of a subtree and vi's are its children (0 ≤ u, vi ≤ n-1).

Every test case will be followed by a blank line. Input ends with a case n=0, which should not be processed.

Output

For each test case print the minimum sum of colors that can be achieved by some proper coloring of the tree.

Sample Input

2
0:
1: 0

8
0: 1 2 3
1: 4 5
2:
3: 6 7
4:
5:
6:
7:

0

Output for the Sample Input

3
11