가장 높아 보이는 봉우리

산맥을 따라 걷고 있다. 이 산맥에는 1킬로미터마다 봉우리가 하나씩 있고 그 사이에는 아무것도 없어서, 걷는 순서대로 봉우리에 $1$번부터 $N$번까지 번호를 붙인다. 봉우리마다 누워서 쉬며 앞을 바라보면 앞쪽 봉우리 중 하나가 가장 높아 보인다.

가장 높아 보이는 봉우리가 실제로 가장 높은 봉우리는 아니다. 더 높은 봉우리가 가깝고 낮은 봉우리에 가려 보이지 않기도 하고, 내리막을 내려다볼 때는 멀리 있는 봉우리가 가까운 봉우리보다 높아 보이기도 한다.

봉우리 $A$에서 봉우리 $B$가 가장 높아 보인다는 것은 다음 세 조건을 모두 만족한다는 뜻이다. $B$는 $A$보다 앞에 있다. $A$와 $B$ 사이의 봉우리는 모두 $A$의 꼭대기와 $B$의 꼭대기를 잇는 직선보다 엄격히 아래에 있다. $B$보다 뒤에 있는 봉우리는 모두 그 직선 위에 있거나 그보다 아래에 있다.

그림에서는 $1$번 봉우리와 $3$번 봉우리에서 $4$번 봉우리가 가장 높아 보인다. $2$번 봉우리에 누우면 $3$번 봉우리에 가려 $4$번 봉우리가 보이지 않으므로 $3$번 봉우리가 가장 높아 보인다.

봉우리의 높이는 모르지만 어느 봉우리에서 어느 봉우리가 가장 높아 보였는지는 모두 기억한다. 이 기억과 어긋나지 않는 높이를 정하라. 누운 채로 보았으므로 모든 관측은 그 봉우리의 지면 높이에서 이루어졌다고 본다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 두 줄이다. 첫째 줄에 봉우리의 개수 $N$이 주어진다. 여행은 $1$번 봉우리에서 시작해 $N$번 봉우리에서 끝난다. 둘째 줄에 $N - 1$개의 수 $x_1, x_2, \dots, x_{N-1}$이 주어진다. $x_i$는 $i$번 봉우리에서 가장 높아 보인 봉우리의 번호다. $N$번 봉우리는 마지막이므로 기록이 없다.

각 테스트 케이스마다 Case #n: y1 y2 ... yN 형식으로 한 줄을 출력한다. n은 $1$부터 시작하는 테스트 케이스 번호이고, $y_i$는 $i$번 봉우리의 높이다. 모든 높이는 $0$ 이상 $10^9$ 이하의 정수여야 한다.

같은 기억에 들어맞는 높이 배정이 여럿일 수 있으므로 그중 사전순으로 가장 앞서는 것을 출력한다. 두 수열 $y$와 $z$가 처음으로 달라지는 자리에서 $y$의 값이 더 작으면 $y$가 사전순으로 앞선다.

기억에 들어맞는 높이 배정이 없으면 대신 Case #n: Impossible을 출력한다.

• $1 \le T \le 30$
• $2 \le N \le 10$
• $i < x_i \le N$