문제

n명의 마법소녀가 원형으로 앉아 있으며, 시계 방향으로 1부터 n까지 번호가 매겨져 있습니다. 이들 중 일부는 마녀입니다. 앞으로 n-3일 동안 다음과 같은 사건이 순서대로 발생합니다.

• 밤에, 정확히 한 명의 마녀가 일어나서 자신의 왼쪽 또는 오른쪽에 있는 첫 번째 살아있는 마법소녀를 죽입니다 (이 사람은 마녀일 수도 있습니다).
• 아침에, 모두가 일어나 죽은 마법소녀를 발견합니다.

마법소녀 재판관인 카모메는 각 아침에 죽은 마법소녀가 발견된 후, 첫날에 존재했을 수 있는 마녀의 최소 수를 찾아야 합니다.

그림 1: 재판

입력

각 테스트 케이스에는 여러 개의 테스트 케이스가 포함됩니다. 첫 번째 줄에는 테스트 케이스의 수 t ($1 \le t \le 10^5$)가 주어집니다. 테스트 케이스 설명이 이어집니다. 첫 번째 줄에는 마법소녀의 수 n ($4 \le n \le 2 \times 10^5$, $1 < \sum n \le 10^6$)이 주어집니다. 두 번째 줄에는 n-3개의 정수 $p_i$ ($1 \le p_i \le n$, $p_i \ne p_j$ for $1 < i < j < n-3$)가 주어지며, 이는 i번째 날에 죽은 마법소녀를 나타냅니다.

출력

각 테스트 케이스에 대해, 죽은 마법소녀가 발견된 후 i번째 날에 죽은 마법소녀를 발견한 후 첫날에 존재했을 수 있는 마녀의 최소 수를 나타내는 n-3개의 정수를 한 줄에 출력합니다.

예제

입력 1

5

출력 1

1 1 1 1 1 1

입력 2

6
2 1 3

출력 2

1 1 2 2 3 3 3

입력 3

9
1 2 3 4 5 6

출력 3

1 2 2 3 3 3 3

입력 4

10
1 3 5 7 9 2 4

출력 4

1 2 2 3 3 3 3

입력 5

10
2 5 1 8 10 9 4

출력 5

1 2 2 3 3 3 3

참고

두 번째 테스트 케이스의 세 번째 날에는 첫날에 최소 2명의 마녀가 존재했을 수 있습니다. 가능한 예시는 3번과 4번이 마녀인 경우로, 3번이 첫날에 2번을 죽이고, 3번이 둘째 날에 1번을 죽이고, 4번이 셋째 날에 3번을 죽이는 경우입니다.

그림 2: 가능한 예시