There are $n$ Mahou Shoujo sitting in a circle, numbered clockwise from 1 to $n$. Among them, some are actually Majo. For the next $n-3$ days, the following events occur one by one: In the night, exactly one Majo wakes up and kills the first living Mahou Shoujo on her left or right (this person could also be a Majo). In the morning, everyone wakes up and discovers the dead Mahou Shoujo.

Kamome, as the judge of the Mahou Shoujo, needs to find, after each morning when a dead Mahou Shoujo is discovered, the minimum number of Majo that could have been present on the first day.

Picture 1: The Judgement

输入格式

Each test contains multiple test cases. The first line contains one integer $t$ ($1 \le t \le 10^5$), indicating the number of test cases. The description of the test cases follows.

The first line contains two integers $n$ ($4 \le n \le 2 \times 10^5$, $1 < \sum n \le 10^6$), indicating the number of Mahou Shoujo. The second line contains $n-3$ integers $p_i$ ($1 \le p_i \le n$), indicating the Mahou Shoujo who died on the $i$-th day.

输出格式

For each test case, output one line containing $n-3$ integers, indicating the minimum number of Majo that could have been present on the first day after discovering the dead Mahou Shoujo on the $i$-th day.

样例

输入 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

说明

For the second test case, on the third day, at least 2 Majo could have been present on the first day. A possible example is 3 and 4 being the Majo, where 3 kills 2 on the first day, 3 kills 1 on the second day, and 4 kills 3 on the third day.

Picture 2: A possible example