Let's define a function $f(a)$ for an array $a$ of length $n$ as $$f(a) = \textrm{cost} + (a_1 - a_2 + a_3 - a_4 \cdots a_n)$$ where $\textrm{cost}$ is zero initially.

Now consider the scenario where Alice and Bob are given an array $a$ of length $n$. They play a game taking at most $10^{100}$ turns alternately with Alice going first.

In each turn, they must perform any one (only one) of the following operations:

• End the game for both Alice and Bob.
• Choose two indices $l,r$ with $1 \le l \le r \le n$ and swap $a_l$ and $a_r$; this adds $(r - l)$ to the $\textrm{cost}$.

Assume that Alice tries to maximize $f(a)$ and Bob tries to minimize it.

Your task is to determine the final value of $f(a)$ assuming both players play optimally.

Input

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 a single integer $n$ ($1 \le n \le 2\cdot10^5$) — the length of the array $a$.

The second line contains $n$ integers $a_1,a_2,a_3,\ldots,a_n$ ($1 \le a_i \le 10^9$) — the elements of the array $a$.

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

Output

For each testcase, output a single integer — the final value of $f(a)$ assuming both players play optimally.

Note

For the first testcase, it is optimal for Alice to end the game on her first turn.

So the final value of $\textrm{cost} = 0$ and $f(a) = 0 + 1000 - 1 = 999$.

For the fourth testcase, it is optimal for Alice to swap $a_1$ and $a_6$, and then it is optimal for Bob to end the game on his first turn.

So the final value of $\textrm{cost} = 5$ and $f(a) = 5 + 15 - 14 + 1 - 14 + 1 - 1=-7$.