[Solution] Smilo and Monsters solution codeforces

Smilo and Monsters solution codeforces
time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

A boy called Smilo is playing a new game! In the game, there are n hordes of monsters, and the i-th horde contains ai�� monsters. The goal of the game is to destroy all the monsters. To do this, you have two types of attacks and a combo counter x, initially set to 00:

• The first type: you choose a number i from 11 to n, such that there is at least one monster left in the horde with the number i. Then, you kill one monster from horde number i, and the combo counter x increases by 11.
• The second type: you choose a number i from 11 to n, such that there are at least x monsters left in the horde with number i. Then, you use an ultimate attack and kill x monsters from the horde with number i. After that, x is reset to zero.

Your task is to destroy all of the monsters, meaning that there should be no monsters left in any of the hordes. Smilo wants to win as quickly as possible, so he wants to the minimum number of attacks required to win the game.

Input

The first line contains a single integer t (1t1041≤�≤104) — the number of test cases. The descriptions of the test cases follow.

The first line of each input data set contains a single integer n (1n21051≤�≤2⋅105) — the number of hordes of monsters.

The second line contains n integers a1,a2,,an�1,�2,…,�� (1ai1091≤��≤109) — the number of monsters in each horde.

It is guaranteed that the sum of n across all test cases does not exceed 21052⋅105.

Output

For each test case, out put the minimum number of attacks required to kill all monsters.

Example
input

Copy
4
4
1 3 1 1
4
1 2 1 1
6
3 2 1 5 2 4
2
1 6
output

Copy
4
4
11
5

Note

In the first test case, we can use an attack of the first type on the 11-st, 33-rd and 44-th hordes, and then use an attack of the second type to finish off the 22-nd horde. We need 44 attacks in total.

In the second test case, we can use an attack of the first type on the 11-st and 33-rd hordes, then use an attack of the second type to finish off the 22-nd horde, and then use an attack of the first type on the 44-th horde. We need 44 attacks in total.

In the fourth test case, we can use an attack of the first type once on the 11-st horde, twice on the 22-nd horde, and then use an attack of the second type on the 22-nd horde, and finally use an attack of the first type to finish off the 22-nd horde. We need 55 attacks in total.