CF1775E.The Human Equation

Petya and his friend, the robot Petya++, went to BFDMONCON, where the costume contest is taking place today.

While walking through the festival, they came across a scientific stand named after Professor Oak and Golfball, where they were asked to solve an interesting problem.

Given a sequence of numbers $a_1, a_2, \dots, a_n$ you can perform several operations on this sequence.

Each operation should look as follows. You choose some subsequence$^\dagger$. Then you call all the numbers at odd positions in this subsequence northern, and all the numbers at even positions in this subsequence southern. In this case, only the position of the number in the subsequence is taken into account, not in the original sequence.

For example, consider the sequence $1, 4, 2, 8, 5, 7, 3, 6, 9$ and its subsequence (shown in bold) $1, \mathbf{4}, \mathbf{2}, 8, \mathbf{5}, 7, 3, \mathbf{6}, 9$. Then the numbers $4$ and $5$ are northern, and the numbers $2$ and $6$ are southern.

After that, you can do one of the following:

• add $1$ to all northern numbers and subtract $1$ from all south numbers; or
• add $1$ to all southern numbers and subtract $1$ from all northern numbers.

Thus, from the sequence $1, \mathbf{4}, \mathbf{2}, 8, \mathbf{5}, 7, 3, \mathbf{6}, 9$, if you choose the subsequence shown in bold, you can get either $1, \mathbf{5}, \mathbf{1}, 8, \mathbf{6}, 7, 3, \mathbf{5}, 9$ or $1, \mathbf{3}, \mathbf{3}, 8, \mathbf{4}, 7, 3, \mathbf{7}, 9$.

Then the operation ends. Note also that all operations are independent, i. e. the numbers are no longer called northern or southern when one operation ends.

It is necessary to turn all the numbers of the sequence into zeros using the operations described above. Since there is very little time left before the costume contest, the friends want to know, what is the minimum number of operations required for this.

The friends were unable to solve this problem, so can you help them?

$^\dagger$ A sequence $c$ is a subsequence of a sequence $d$ if $c$ can be obtained from $d$ by the deletion of several (possibly, zero or all) elements.

佩特亚和他的朋友——机器人佩特亚++，前往了正在举办服装大赛的 BFDMONCON。

在游逛节会时，他们偶然发现了一个以大木教授与高尔夫球教授命名的科学展台，展台工作人员请他们解决一个有趣的题目。

给定一个数字序列 $a_1, a_2, \dots, a_n$，你可以在该序列上执行若干次操作。

每次操作需按如下方式进行：你选择该序列的一个子序列$^\dagger$。接着，将该子序列中所有位于奇数位置上的数称为“北方数”，将所有位于偶数位置上的数称为“南方数”。注意：此处的位置编号仅针对所选子序列本身，而非原序列中的位置。

例如，考虑序列 $1, 4, 2, 8, 5, 7, 3, 6, 9$ 及其一个子序列（加粗显示）：$1, \mathbf{4}, \mathbf{2}, 8, \mathbf{5}, 7, 3, \mathbf{6}, 9$。那么，数字 $4$ 和 $5$ 是北方数，而数字 $2$ 和 $6$ 是南方数。

随后，你可以执行以下两种操作之一：

• 将所有北方数加 $1$，同时将所有南方数减 $1$；或者
• 将所有南方数加 $1$，同时将所有北方数减 $1$。

因此，对于序列 $1, \mathbf{4}, \mathbf{2}, 8, \mathbf{5}, 7, 3, \mathbf{6}, 9$，若选择上述加粗所示的子序列，则可得到以下两种结果之一：
$1, \mathbf{5}, \mathbf{1}, 8, \mathbf{6}, 7, 3, \mathbf{5}, 9$ 或 $1, \mathbf{3}, \mathbf{3}, 8, \mathbf{4}, 7, 3, \mathbf{7}, 9$。

至此，本次操作结束。还需注意：所有操作彼此独立，即一次操作结束后，“北方数”与“南方数”的称谓即失效，不再延续至后续操作。

目标是通过上述操作，将序列中所有数字变为零。由于距离服装大赛开始时间所剩无几，两位朋友想知道：完成该目标所需的最少操作次数是多少？

两位朋友未能解出此题，你能帮帮他们吗？

$^\dagger$ 序列 $c$ 是序列 $d$ 的一个子序列，当且仅当 $c$ 可通过对 $d$ 删除若干（可能为零个或全部）元素而得到。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

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

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$) — the description of the sequence itself.

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

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2\cdot 10^5$）—— 表示序列的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-10^9 \le a_i \le 10^9$）—— 表示该序列本身。

保证所有测试用例的 $n$ 值之和不超过 $2\cdot 10^5$。

For each test case, print one integer in a single line — the minimum number of operations it takes to turn all the numbers into zeros.

对于每个测试用例，在一行中输出一个整数——将所有数字变为零所需的最少操作次数。

In the first test case, the sequence of operations is as follows: $\mathbf{1}, 2, \mathbf{-3} \longrightarrow 0, \mathbf{2}, \mathbf{-2} \longrightarrow 0, \mathbf{1}, \mathbf{-1} \longrightarrow 0, 0, 0$.

In the second test case, the sequence looks like this: $\mathbf{1}, 0, 0, \mathbf{-1}, -1 \longrightarrow 0, 0, 0, 0, \mathbf{-1} \longrightarrow 0, 0, 0, 0, 0$.

In the fourth test case, simply select the entire sequence as a subsequence, then subtract one from the northern numbers and add one to the southern numbers. Thus, the sequence will be nulled in one operation.

In the fifth test case, you don't need to do any operations, since the sequence already consists of zeros.

在第一个测试用例中，操作序列为：$\mathbf{1}, 2, \mathbf{-3} \longrightarrow 0, \mathbf{2}, \mathbf{-2} \longrightarrow 0, \mathbf{1}, \mathbf{-1} \longrightarrow 0, 0, 0$。

在第二个测试用例中，操作序列为：$\mathbf{1}, 0, 0, \mathbf{-1}, -1 \longrightarrow 0, 0, 0, 0, \mathbf{-1} \longrightarrow 0, 0, 0, 0, 0$。

在第四个测试用例中，只需将整个序列选为子序列，然后对北部数字减一、对南部数字加一。因此，该序列可在一次操作中被清零。

在第五个测试用例中，无需执行任何操作，因为序列本身已全为零。