Background

Special for beginners, ^_^

Description

在一个夜黑风高的晚上，有 $n(n \le 1000)$ 个小朋友在桥的这边，现在他们需要过桥，但是由于桥很窄，每次只允许不大于两人通过，他们只有一个手电筒，所以每次两个人过桥后，需要有 1 人把手电筒带回来，问过河所需最短时间。

Format

Input

输入 $t$ 组数据，每组数据第 $1$ 行输入 $n(n<1000)$，第 $2$ 行输入 $n$ 个数，表示每个人过河的时间。

Output

输出 $t$ 行数据，每行 $1$ 个数，表示每组过河最少时间。

Samples

1
4
1 2 5 10

17

Limitation

1s, 1024KiB for each test case.