In this problem, you need to solve a famous NP-hard problem: the isotonic regression problem.

The isotonic regression problem requires variables: you need to provide an integer sequence $(x_1, x_2, \ldots, x_n)$ of length $n$ that satisfies all the conditions below.

The isotonic regression problem requires constraints: general isotonic regression problems require maintaining a partial order, but that would be a standard template problem. Therefore, in this problem, you only need to ensure that $\prod_{i=1}^n x_i > 0$.

The isotonic regression problem requires an objective function: that is, the regression cost. Similar to other $L_1$ isotonic regression problems, given $n$ integer target parameters $y_1, y_2, \ldots, y_n$, you need to minimize $\sum_{i=1}^n |x_i - y_i|$.

The isotonic regression problem does not necessarily have multiple queries, and this problem does not either, but each test case contains multiple test data sets.

Input

The first line contains an integer $T$, representing the number of test cases.

Read $T$ test cases sequentially. For each test case:

• The first line contains an integer $n$.
• The second line contains $n$ space-separated integers, which are $y_1, y_2, \ldots, y_n$ in order.

Output

Output $T$ lines, each containing an integer, representing the answer for each test case in order.

Examples

Input 1

3
3
-3 -2 -2
9
9 9 8 2 4 4 3 5 3
3
0 0 0

Output 1

3
0
3

Note

For the first test case, one sequence $(x_1, x_2, x_3)$ that satisfies the condition is $(-3, 1, -2)$. It satisfies $\prod_{i=1}^n x_i = (-3) \times 1 \times (-2) = 6 > 0$, and its regression cost is $\sum_{i=1}^n |x_i - y_i| = |(-3) - (-3)| + |1 - (-2)| + |(-2) - (-2)| = 3$. It can be proven that there is no valid sequence with a regression cost $< 3$, so the answer is $3$.

For the third test case, one sequence that satisfies the condition is $(1, -1, -1)$.

Input 2

(input data)

Output 2

(output data)

Constraints

There are $10$ test cases in this problem, each worth $10$ points.

Let $\sum n$ be the sum of $n$ over all test data in a test case.

For all test cases, it is guaranteed that $1 \le T, n, \sum n \le 2 \times 10^5$ and $-10^9 \le y_i \le 10^9$.

For test case $1$, it is guaranteed that $T, n, |y_i| \le 5$.

For test cases $2, 3$, it is guaranteed that $\sum n, |y_i| \le 100$.

For test cases $4, 5$, it is guaranteed that $\sum n, |y_i| \le 1000$.

For test case $6$, it is guaranteed that for each test data set, $\prod_{i=1}^n y_i \ne 0$.

For test case $7$, it is guaranteed that for each test data set, $\prod_{i=1}^n y_i = 0$.

For test cases $8, 9, 10$, there are no special restrictions.