Moloco 是一家广告技术公司，致力于帮助全球各地的公司改善其在线广告。通过使用 Moloco 的技术，互联网用户可以观看到更相关的广告，广告商也可以更有效地推广他们的产品。

Moloco 的自动广告投放系统实时对待处理的广告请求进行分组，以最大化效率。每个广告请求都关联着一个正整数，表示处理该请求所需的开销。给定队列中 $N$ 个待处理的请求，系统通过重复以下步骤来处理所有请求：

• 检查当前待处理队列最前面的最多 3 个请求。从中选择 2 个请求并一起处理，然后将它们都从队列中移除。需要支付的开销是处理这两个请求所需开销的最大值。
• 如果当前待处理队列中只有一个请求，则处理并将其从队列中移除。在这种情况下，开销就是处理该请求所需的开销。

求系统处理所有广告请求所需的最小总开销。

输入格式

输入的第一行包含一个整数 $T$，表示测试用例的数量。($1 \le T \le 50\,000$)

每个测试用例的第一行包含一个整数 $N$，表示广告请求的数量。($1 \le N \le 1\,000\,000$)

第二行包含 $N$ 个空格分隔的整数 $A_1, A_2, \dots, A_N$，表示处理每个请求所需的开销。($1 \le A_i \le 10^9$)

所有测试用例的 $N$ 之和不超过 $1\,000\,000$。

输出格式

对于每个测试用例，单行输出所需的最小总开销。

样例

输入格式 1

2
5
1 6 3 2 5
2
314 1592

输出格式 1

11
1592