A. Assigning Distinct Integers
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given $$$n$$$ positive integers $$$a_1,a_2,\dots,a_n$$$.

Construct a sequence of $$$n$$$ pairwise distinct positive integers $$$b_1,b_2,\dots,b_n$$$ such that $$$b_i\ge a_i$$$ for every $$$1\le i\le n$$$. First, minimize $$$\sum_{i=1}^{n}b_i$$$. Among all sequences with the minimum sum, output the lexicographically smallest one.

A sequence $$$(x_1,x_2,\dots,x_n)$$$ is lexicographically smaller than $$$(y_1,y_2,\dots,y_n)$$$ if there is an index $$$p$$$ such that $$$x_i=y_i$$$ for every $$$1\le i \lt p$$$, and $$$x_p \lt y_p$$$.

Input

The first line contains an integer $$$T$$$ ($$$1\le T\le 10^4$$$), the number of test cases.

For each test case:

  • The first line contains an integer $$$n$$$ ($$$1\le n\le 3\times 10^5$$$).
  • The second line contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ ($$$1\le a_i\le 10^9$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3\times 10^5$$$.

Output

For each test case, output one line containing $$$n$$$ integers $$$b_1,b_2,\dots,b_n$$$, separated by single spaces.

Example
Input
3
3
1 1 1
5
5 3 5 3 5
3
2 1 1
Output
1 2 3
5 3 6 4 7
2 1 3
Note

In the first test case, the minimum possible sum is $$$1+2+3=6$$$.

In the third test case, every optimal sequence uses the values $$$1,2,3$$$. The lexicographically smallest valid order is $$$(2,1,3)$$$.