Description

给定多组数据，每组数据由一个长度为 $n$ 的数组 $a$ 构成$(1 \leq a_i \leq 10^9)$。

你可以对数组进行如下操作：

选择一个连续的子区间 $[l, r]$ ，将这个区间内的所有元素都 加上 $1$ 或 减去 $1$。

你的目标是将数组中的 $\bf{所有数字}$ 变为 $0$ 。请你计算，使数组中所有数字变为 $0$ 的 $\bf{最少操作次数}$ 。

Format

Input

本题有多组测试数据。

第一行有一个整数 $t\ (1\leq t \leq 200000)$，表示测试用例数。

接来下 $t$ 组数据，每组数据包含两行:

第一行:一个整数 $n$($1\leq n\leq 2\times 10^5$)，表示数组 $a$ 的长度。

第二行: $n$ 个整数 $a_1,a_2,\cdots,a_n\ (1 \leq a_i \leq 10^9)$，表示数组$a$的元素。

所有测试用例中 $n$ 的总和满足 $\sum n \leq2 \times 10^5$

Output

应输出 $t$ 行。

第 $i$ 行输出一个整数，表示输入第 $i$ 组数据的最少操作次数。

Samples

1
5
2 3 4 5 6

6

Limitation

1s, 1024KiB for each test case.