题目内容

给定一个长度为 $n$ 的整数数组 $a_1,a_2,\cdots,a_n$。

你需要从中选出一个子序列 $b_1,b_2,\cdots,b_m$（保持相对顺序，不一定连续），使得目标值

$F(b)=\sum_{i=1}^{m}(-1)^{i-1}b_i$最大。

【子序列】子序列为从原序列中删除任意个（可以为零，可以为全部）元素得到的新序列。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T$（$1\le T\le 2\times 10^5$）代表数据组数，每组测试数据描述如下：

• 每组第一行输入一个整数 $n$（$1\le n\le 2\times 10^5$）；
• 第二行输入 $n$ 个整数 $a_1,\ldots,a_n$​（$\lvert a_i\rvert \le 10^6$）。

保证所有测试中 $n$ 的总和不超过 $5\times 10^5$。

输出描述

对于每组测试数据，输出一行一个整数，表示最大可能的 $F(b)$。

示例 1

输入

3
3
1 2 3
5
-1 2 -3 4 -5
4
5 5 5 5

输出

3
14
5