Maram loves counting people that are standing in a queue, once she was in the college and noticed a very long queue. All the people in the queue were waiting for their turn to have their 84 L.E. prize for completing secondary school. Maram wondered, for each student standing in the queue, how many students with the same height are standing behind him, and how many are standings in front of him.

Help Maram with this task.

Input

The first line contains a single integer T – the number of test cases (1 <= T <= 10). Each test case consists of two lines, the first line contains one integer N (1 <= N <= 10⁵) – the number of students standing in the queue, then follows N integers, N_i (1 <= N_i <= 10⁶) is the height of the i-th student.

Output

For each test case, output N lines, each line contains 2 space separated integers – the number of students behind the i-th student with the same height, and the number of students in front of the i-th student with the same height.

Print a blank line after each test case.

Example

Input:
2
3
1 2 3
12
1 9 4 6 9 1 5 4 9 3 7 1

Output:
0 0
0 0
0 0

0 2
0 2
0 1
0 0
1 1
1 1
0 0
1 0
2 0
0 0
0 0
2 0

Note:
Due to large output, you may use faster output method (like printf for C++)