B. Twin Works
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The Arriaga Museum is going to replace its old system of codes assigned to the works with a new, clearer, and more organized one.

Some pieces are twin works. They are pairs of pieces that share exactly the same code because they are practically identical. In the new system, this must be maintained: two works that had the same old code must retain the same new code, and works with different codes cannot share one.

The works are placed in a long hallway in a fixed order that cannot be modified. From time to time, Mr. Ernesto Lafuente, the catalog inspector, walks down the hallway reviewing the works in that same order. It is much more convenient for him if, as he progresses, the codes he reads tend to appear in increasing order.

The Board wants to assign the new codes in such a way that, while respecting exactly the same groups of twin works as the old system, the number of times a greater code appears before a lesser one in the walkthrough is minimized.

Help them by constructing a code assignment that minimizes that number. The new codes must:

  • Maintain exactly the same groups of twin works as the old codes.
  • Minimize the number of pairs of positions $$$i \lt j$$$ where the code at position $$$i$$$ is greater than the code at position $$$j$$$, known as an inversion.

If there are multiple optimal solutions, any of them will be valid.

Input

The first line contains an integer $$$T$$$, the number of cases to process.

The first line of each case contains $$$n$$$, the number of works placed in the hallway.

The second line contains $$$n$$$ positive integers $$$a_1, a_2, \ldots, a_n$$$, where $$$a_i$$$ is the old code of the work located at position $$$i$$$ in the hallway. Each value appears at most twice.

Output

For each case, you must print a line with $$$n$$$ positive integers, $$$b_1, b_2, \ldots, b_n$$$, representing the new codes assigned to the works to minimize the number of inversions, in the same order as in the hallway. If there are multiple optimal assignments, you can print any of them.

Example
Input
2
3
3 2 1
4
2 1 1 2
Output
1 2 3 
1 2 2 1
Note
  • $$$1 \le T \le 10^5$$$
  • $$$1 \le n \le 10^5$$$
  • The sum of $$$n$$$ across all cases will be at most $$$10^5$$$.
  • $$$1 \le a_i, b_i \le n$$$