Hay $n$ Mahou Shoujo ngồi thành một vòng tròn, được đánh số theo chiều kim đồng hồ từ 1 đến $n$. Trong số đó, một số thực chất là Majo.

Trong $n-3$ ngày tiếp theo, các sự kiện sau đây diễn ra lần lượt:

• Vào ban đêm, chính xác một Majo thức dậy và giết Mahou Shoujo đầu tiên còn sống ở bên trái hoặc bên phải của cô ta (người này cũng có thể là một Majo).
• Vào buổi sáng, tất cả mọi người thức dậy và phát hiện ra Mahou Shoujo đã chết.

Kamome, với tư cách là thẩm phán của các Mahou Shoujo, cần tìm ra, sau mỗi buổi sáng khi một Mahou Shoujo chết được phát hiện, số lượng Majo tối thiểu có thể đã có mặt vào ngày đầu tiên.

Hình 1: Sự phán xét

Dữ liệu vào

Mỗi trường hợp kiểm tra chứa nhiều trường hợp kiểm tra. Dòng đầu tiên chứa một số nguyên $t$ ($1 \le t \le 10^5$), cho biết số lượng trường hợp kiểm tra. Mô tả các trường hợp kiểm tra tiếp theo.

Dòng đầu tiên chứa hai số nguyên $n$ ($4 \le n \le 2 \times 10^5$, $1 < \sum n \le 10^6$), cho biết số lượng Mahou Shoujo.

Dòng thứ hai chứa $n-3$ số nguyên $p_i$ ($1 \le p_i \le n$, $p_i \ne p_j$ với $1 < i < j < n-3$), cho biết Mahou Shoujo đã chết vào ngày thứ $i$.

Dữ liệu ra

Với mỗi trường hợp kiểm tra, in ra một dòng chứa $n-3$ số nguyên, cho biết số lượng Majo tối thiểu có thể đã có mặt vào ngày đầu tiên sau khi phát hiện Mahou Shoujo chết vào ngày thứ $i$.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

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

Ghi chú

Đối với trường hợp kiểm tra thứ hai, vào ngày thứ ba, có ít nhất 2 Majo có thể đã có mặt vào ngày đầu tiên. Một ví dụ khả thi là 3 và 4 là Majo, trong đó 3 giết 2 vào ngày đầu tiên, 3 giết 1 vào ngày thứ hai và 4 giết 3 vào ngày thứ ba.

Hình 2: Một ví dụ khả thi