# Friends

Time Limit: 1s

Memory Limit: 65535k

## Description

In a country, the relationship between people can be indicated by a tree. If two people are acquainted with each other, there will be an edge between them. If a person can get in touch with another through no more than five people, we should consider these two people can become friends. Now, give you a tree of N people’s relationship. ( 1 <= N <= 1e5), you should compute the number of who can become friends of each people?

## Input

In the first line, there is an integer T, indicates the number of the cases. For each case, there is an integer N indicates the number of people in the first line. In the next N-1 lines, there are two integers u and v, indicate the people u and the people v are acquainted with each other directly. People labels from 1.

## Output

For each case, the first line is “Case #k :”, k indicates the case number. In the next N lines, there is an integer in each line, indicates the number of people who can become the ith person’s friends. i is from 1 to n.

## Sample Input

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

## Sample Output

Case #1:
6
7
7
7
7
7
7
6

None

None