问题描述

给你一个长度为 $n$ 的数组 $a$ ，其中的元素满足 ${0 \le a_i \le n}$ 。您最多可以进行 $1$ 次以下操作：

• 选择两个索引 $i$ 和 $j$ ，使得 $i \lt j$ .设置 $a_i = a_i + a_j$ 。然后，设 $a_j = 0$ .

输出 $\min(a_1) + \min(a_1,a_2) + … + \min(a_1, a_2, … , a_n)$ 可能得到的最小值。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ( $1 \le t \le 10^3$ )。测试用例说明如下。

每个测试用例的第一行包含一个整数 $n$ ( $2 \leq n \leq 2\cdot 10^5$ ) 表示 $a$ 的长度。

下一行包含 $n$ 个空格分隔的整数 $a_1, a_2, \ldots, a_n$ ( $0 \le a_i \le n$ ) 表示数组 $a$ 。

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

输出格式

针对每个测试用例，在新行中输出一个整数，最小值为 $min(a_1) + min(a_1,a_2) + \ldots + min(a_1, a_2, \ldots, a_n)$ 。

样例输入

3
2
1 2
3
1 2 3
4
3 0 2 3

样例输出

2
2
3

说明

在第二个测试用例中，最好使用 $i=2$ 和 $j=3$ 执行操作。

在第三个测试用例中，不执行任何操作是最佳选择。答案是 $3$ 。