$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$, $1 < i < j < n-3$일 때 $p_i \ne p_j$)가 주어지며, 이는 $i$번째 날에 죽은 마법소녀를 나타냅니다.

출력

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

예제

입력 1

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

출력 1

1 1 1 1 1
1 1 2 2 3 3 3
1 2 2 3 3 3 3

참고

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

그림 2: 가능한 예시