스테리 스카이☆퍼레이드

우나와 당신은 $N$개의 별로 별자리를 만들려고 한다.

먼저 우나는 별자리를 만들기 위한 도안을 만든다. 도안은 $N$개의 별을 정점으로 하는 무방향 그래프이며, 각 별에는 $1$부터 $N$까지 서로 다른 번호가 붙어 있다. 우나는 항상 다음 과정으로 도안을 만든다.

처음에는 별 하나만 존재한다. 이후 나머지 $N-1$개의 별을 임의의 순서로 하나씩 추가한다. 별을 추가할 때마다 다음 두 방법 중 하나를 선택한다.

• 새 별을 현재 존재하는 모든 별과 연결한다.
• 새 별을 현재 존재하는 어떤 별과도 연결하지 않는다.

우나가 도안을 완성하면, 당신은 각 별 $i$의 밝기 $A_i$를 $1$ 이상 $N$ 이하의 정수로 정한다. 서로 다른 두 별 $u,v$는

일 때, 그리고 그때에만 빛으로 연결된다.

빛으로 연결된 두 별을 간선으로 하는 그래프가 우나의 도안과 정확히 같아지도록 밝기 $A_1,A_2,\ldots,A_N$을 정하여라.

조건을 만족하는 밝기 배정이 항상 존재하는 입력만 주어진다.

입력은 다음과 같은 형식으로 주어진다.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

각 테스트 케이스마다 조건을 만족하는 $N$개의 정수 $A_1,A_2,\ldots,A_N$을 한 줄에 출력한다.

• $1\leq T\leq10\,000$.
• $1\leq N\leq100\,000$.
• $0\le M\le$.