有 $n$ 名魔法少女围坐成一个圆圈，按顺时针方向依次编号为 $1$ 至 $n$。她们之中，有些人实际上是魔女。

在接下来的 $n-3$ 天里，依次发生以下事件：

• 在夜晚，恰好有一名魔女醒来，杀死她左侧或右侧第一位存活的魔法少女（这个人也可能是魔女）。
• 在早晨，所有人醒来并发现被杀害的魔法少女。

作为魔法少女裁判的鸥（Kamome），需要在每天早晨发现被杀害的魔法少女后，求出第一天可能存在的魔女的最少数量。

图 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$ 天死亡的魔法少女。

输出格式

对于每个测试用例，输出一行包含 $n-3$ 个整数，表示在第 $i$ 天发现被杀害的魔法少女后，第一天可能存在的魔女的最少数量。

样例

输入格式 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：一个可能的示例