Chika is playing a game!

Chika got her ~N~ friends arranged in a circle and gave them each a card labelled with a distinct number from ~1~ to ~N~.

The game is to figure out who has which card. However, if you ask someone what card they have, they will instead reply with the minimum label of their neighbours' cards (for some reason). You have asked everyone for their answers and have recorded them in your array ~a~.

Chika already knows the answers—because she cheated. You, however, must figure out the answer. It occurs to you that the answer is not always unique; that is, even if you ask everyone, there may be multiple valid configurations that are consistent with the answers.

As such, you decide to only declare a card's value when you are convinced of it, formally, when across all configurations consistent with the answers given, the person always has the same card.

In order to have the most fun, Chika has decreed that you will play ~T~ games and must answer for each.

Constraints

~1 \le T \le 10^6~

~3 \le N \le 10^6~

~1 \le a_i \le N~

It is guaranteed that there is a valid arrangement of the integers from ~1~ to ~N~ that produce the array ~a~.

The sum of ~N~ across all test cases will not exceed ~10^6~.

Subtask 1 [10%]

~3 \le N \le 9~

The sum of ~N~ across all test cases will not exceed ~10^5~.

Subtask 2 [30%]

The sum of ~N~ across all test cases will not exceed ~2 \times 10^3~.

Subtask 3 [60%]

No additional constraints.

Input Specification

The first line contains the integer ~T~.

The next ~2T~ lines contain games. For each game, the first line contains the integer ~N~, and the next line contains ~N~ integers ~a_i~, the responses from Chika's friends.

Output Specification

For each game, output an array of length ~N~, where the ~i~th element is either the number on the card of the ~i~th person or ~0~ if the number varies across valid configurations.

Sample Input

2
5
1 3 1 4 2
4
1 3 1 3

Sample Output

3 1 0 2 0
0 0 0 0

Explanation

It can be proven that the only two valid configurations for the first game are 3 1 4 2 5 and 3 1 5 2 4.