크리스마스 트리의 마트료시카

크리스마스가 아직 한 달 남았지만 판다 씨는 벌써 크리스마스 준비를 시작했다. 판다 씨는 마트료시카 인형 한 세트로 크리스마스 트리를 장식한다. 번호가 $1, 2, \ldots, n$인 마트료시카 인형이 $n$개 있다. $i$번 인형은 모든 $1 \le i \le n - 1$에 대해 ${(i+1)}$번 인형 안에 완벽하게 들어가도록 만들어졌다. 인형은 번호가 이웃할 때만 안정적으로 겹쳐지며, 그렇지 않으면 작은 인형이 큰 인형 밖으로 미끄러져 나온다. 인형은 재귀적으로 겹칠 수 있다. 예를 들어 $n$개의 인형을 가장 작은 것부터 가장 큰 것까지 차곡차곡 겹치면 인형 하나만 남을 때까지 겹칠 수 있다.

크리스마스 트리에는 마침 $n$개의 노드가 있고, 각 노드에 마트료시카 인형이 하나씩 매달려 있다. $1$번 인형은 트리 루트에 놓인다. 판다 씨는 크리스마스 이브에 친구 양 씨를 초대해 트리에서 인형 몇 개를 선물로 가져가게 한다. 양 씨는 트리 노드 하나를 고르고, 그 노드를 루트로 하는 서브트리에 있는 인형을 전부 모은다.

인형이 많을 수 있으므로 양 씨는 모은 인형을 들고 다니기 쉽게 겹쳐 두려고 한다. 각 트리 노드마다 인형을 최대한 많이 겹쳤을 때 최종적으로 몇 개가 남는지 궁금해한다. 인형은 안정적으로 겹쳐져야 한다.

첫 줄에 테스트 케이스의 수 $T$가 주어진다 ($1 \le T \le 10$). 이어서 $T$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫 줄에는 정수 $n$이 주어진다 ($1 \le n \le 2 \times 10^5$). $n$은 인형의 수이자 트리 노드의 수이다.

다음 $(n-1)$개 줄에는 각각 두 정수 $x$와 $y$가 주어진다 ($1 \le x, y \le n$). 이는 $x$번 인형과 $y$번 인형이 크리스마스 트리에서 이웃한다는 뜻이다.

모든 테스트 케이스에서 $n$의 합은 $10^6$을 넘지 않는다.

각 테스트 케이스마다 한 줄을 출력한다. 줄은 "Case #x:"로 시작하며, 여기서 x는 테스트 케이스 번호($1$부터 시작)이다. 이어서 $n$개의 정수를 출력한다. $i$번째 ($1 \le i \le n$) 정수는 양 씨가 $i$번 인형이 있는 트리 노드를 골라 서브트리의 인형을 전부 모은 뒤 최대한 많이 안정적으로 겹쳤을 때 남는 인형의 수이다.