如果一个长度为 $n$ 的数组 $a$ 满足对于每个 $1 < i < n$，都有 $a_i > \max\{a_{i-1}, a_{i+1}\}$ 或 $a_i < \min\{a_{i-1}, a_{i+1}\}$，则称该数组为“波浪形”数组。

给定一个长度为 $n$ 的整数数组 $b$ ($1 \le b_i \le 10^9$)。你希望将该数组变为波浪形。为此，你可以花费一些硬币，每花费一枚硬币，你可以使 $b$ 中的一个元素增加或减少 $1$。请计算使数组变为波浪形所需花费的最少硬币数量。

输入格式

第一行包含测试用例的数量 $T$ ($1 \le T \le 10^3$)。

每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 10^6$)，表示数组 $b$ 的长度。

第二行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$ ($1 \le b_i \le 10^9$)，表示数组 $b$。

保证所有测试用例的 $n$ 之和不超过 $3 \times 10^6$。

输出格式

对于每个测试用例，输出一个整数，表示使数组变为波浪形所需花费的最少硬币数量。

样例

样例输入 1

3
4
1 7 6 5
6
1 2 3 4 5 6
6
1 1 4 5 1 4

样例输出 1

2
4
4