캔버스 색칠

지난해의 성공 이후 사무엘 W. E. R. 크래프트는 이름이 더 널리 알려졌고, 이제 머릿속에 떠오르는 기획을 모두 실행할 자금이 있다. 이번 기획은 같은 색이 두 번 나오지 않도록 칠한 캔버스를 한 줄로 늘어놓는 것이다.

사무엘은 크기가 제각각인 흰색 캔버스를 여러 장 샀다. 손으로 칠하면 시간이 너무 오래 걸리므로, 칠하는 작업을 자동으로 처리하는 커다란 기계를 만들었다. 기계는 다음 순서로 동작한다.

1. 캔버스를 원하는 순서로 골라 기계의 컨베이어 벨트 위에 한 줄로 놓는다.
2. 색 $C$와, 그때 색 $C$인 캔버스의 수보다 작은 수 $F$를 고른다.
3. 왼쪽에서 오른쪽으로 가면서 색 $C$인 캔버스를 모두 다시 칠한다. 앞쪽 $F$장은 새로운 색 $X$로, 나머지는 새로운 색 $Y$로 칠한다. $X$와 $Y$는 기계가 정하며, 서로 다르고 지금까지 쓴 어떤 색과도 다르다. 이 단계에서 쓰는 잉크의 양은 다시 칠한 캔버스의 크기의 합과 같다.
4. 모든 캔버스의 색이 서로 달라질 때까지 2번과 3번을 반복한다.

예를 들어 사무엘이 크기가 3, 5, 5, 7인 캔버스 네 장을 샀다고 하자. 아래 그림은 칠하는 방법 두 가지를 보여 준다.

사무엘이 산 캔버스의 크기가 주어질 때, 모든 캔버스의 색을 서로 다르게 만드는 데 기계가 쓰는 잉크의 최솟값을 구하라.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스는 두 줄이다. 첫째 줄에 캔버스의 수 $N$이 주어지고, 둘째 줄에 캔버스 $N$장의 크기가 공백으로 구분되어 주어진다.

각 테스트 케이스마다 한 줄씩, 모든 캔버스의 색을 서로 다르게 만드는 데 필요한 잉크의 최솟값을 출력한다. 출력은 모두 $T$줄이다.

• $1 \le T \le 100$, 테스트 케이스의 수
• $1 \le N_i \le 100000$, $i$번째 테스트 케이스의 캔버스 수
• $1 \le s \le 100000$, 캔버스 한 장의 크기
• $1 \le \sum_{i=1}^{T} N_i \le 100000$, 입력 파일 하나에 들어 있는 캔버스 수의 합