There are N hidden integer arrays of length N each. You are given the mex of each of these N arrays.

Ashish likes lower bounds and Kryptonix likes upper bounds. So, for each 0 ≤ i ≤ N-1, find:
The least possible number of occurrences of i across all the arrays
The most possible number of occurrences of i across all the arrays

Note that these values must be computed independently, i.e, it is allowed to choose different configurations of arrays to attempt to minimize/maximize the number of occurrences of different integers.

Please see the samples for an example.

Recall that the mex of an array is the smallest non-negative integer that is not present in it. For example, the mex of [0, 2, 4, 1, 1, 5] is 3, and the mex of [3, 8, 101, 99, 100] is 0.

------ Input Format ------

• The first line of input contains a single integer T — the number of test cases. Then the test cases follow.
• The first line of each test case contains an integer N — the size of the array.
• The second line of each test case contains $N space-separated integers A_{1}, A_{2}, \dots, A_{N},$ denoting the mexes of the N arrays.

------ Output Format ------

For each test case, output N lines, each containing two space-separated integers. The i-th line should contain the least and the most possible number of occurrences of i across all the arrays.

------ Constraints ------

$1 ≤ T ≤ 10^{4}$
$1 ≤ N ≤ 3\cdot10^{5}$
$0 ≤ A_{i} ≤ N$
- The sum of $N$ over all test cases does not exceed $3\cdot10^{5}$

----- Sample Input 1 ------
3
2
1 0
5
3 1 5 0 2
3
1 2 1
----- Sample Output 1 ------
1 2
0 2
4 13
3 13
2 13
1 13
1 15
3 8
1 2
0 4
----- explanation 1 ------
Test case $1$: We have the following:
- For $i = 0$, the two arrays can be $[0, 3]$ and $[2, 4]$ giving us one zero, or $[0, 0]$ and $[3, 1]$ giving us $2$ zeros.
- For $i = 1$, $[0, 4]$ and $[3, 4]$ give no ones, while $[0, 9]$ and $[1, 1]$ give $2$ ones.

Test case $3$: We have the following:
- For $i = 0$, the arrays $[0, 3, 2], [1, 0, 4], [5, 0, 2]$ give the least number of zeros (i.e, $3$), and the arrays $[0, 0, 0], [1, 0, 0], [0, 0, 0]$ give the most.
- For $i = 1$, the arrays $[5, 7, 0], [0, 3, 1], [6, 0, 3]$ give the least number of ones and the arrays $[0, 3, 2], [1, 1, 0], [5, 0, 2]$ give the most.
- For $i = 2$, the arrays $[3, 0, 9], [0, 0, 1], [0, 0, 0]$ give the least number of twos and the arrays $[2, 0, 2], [0, 1, 0], [2, 2, 0]$ give the most.

见题面

见题面