You are given $n$ points with integer coordinates $x_1,\dots x_n$, which lie on a number line.

For some integer $s$, we construct segments [$s,x_1$], [$s,x_2$], $\dots$, [$s,x_n$]. Note that if $x_i<s$, then the segment will look like [$x_i,s$]. The segment [$a, b$] covers all integer points $a, a+1, a+2, \dots, b$.

We define the power of a point $p$ as the number of segments that intersect the point with coordinate $p$, denoted as $f_p$.

Your task is to compute $\sum\limits_{p=1}^{10^9}f_p$ for each $s \in \{x_1,\dots,x_n\}$, i.e., the sum of $f_p$ for all integer points from $1$ to $10^9$.

For example, if the initial coordinates are $[1,2,5,7,1]$ and we choose $s=5$, then the segments will be: $[1,5]$,$[2,5]$,$[5,5]$,$[5,7]$,$[1,5]$. And the powers of the points will be: $f_1=2, f_2=3, f_3=3, f_4=3, f_5=5, f_6=1, f_7=1, f_8=0, \dots, f_{10^9}=0$. Their sum is $2+3+3+3+5+1+1=18$.

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

The first line of each test case contains an integer $n$ ($1 \le n \le 2\cdot 10^5$) — the number of points.

The second line contains $n$ integers $x_1,x_2 \dots x_n$ ($1 \le x_i \le 10^9$) — the coordinates of the points.

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

For each test case, output $n$ integers, where the $i$-th integer is equal to the sum of the powers of all points for $s=x_i$.