트리의 차수 수열(모든 정점의 차수를 임의의 순서로 나열한 것)이 주어집니다. 주어진 차수 수열을 가지는 모든 트리 중에서, 최대 매칭(maximum matching)의 크기가 가장 큰 트리를 찾으십시오.

입력

첫 번째 줄에는 테스트 케이스의 수 $t$ ($1 \le t \le 100\,000$)가 주어집니다. 다음 줄부터 $t$개의 테스트 케이스에 대한 설명이 이어집니다. 각 테스트 케이스의 첫 번째 줄에는 정점의 수 $n$ ($2 \le n \le 200\,000$)이 주어집니다. 다음 줄에는 트리의 차수 수열인 $n$개의 정수 $d_1, d_2, \dots, d_n$ ($1 \le d_i \le n - 1$)이 주어집니다. $\sum d_i = 2(n - 1)$임이 보장되며, 주어진 차수 수열을 가지는 트리가 적어도 하나 존재함이 보장됩니다. 또한, 모든 테스트 케이스에 대한 $n$의 총합은 최대 $200\,000$임이 보장됩니다.

출력

각 테스트 케이스마다, 주어진 차수 수열을 가지는 모든 트리 중 가장 큰 최대 매칭의 크기를 정수로 출력하십시오.

예제

입력 1

2
10
1 1 2 2 2 2 2 2 2 2
5
4 1 1 1 1

출력 1

5
1

참고

첫 번째 테스트 케이스에서, 10개의 정점을 가진 경로 그래프(path)를 구성할 수 있으며, 이는 주어진 차수 수열을 만족하면서 가장 큰 최대 매칭을 가집니다. 두 번째 테스트 케이스에서, 가능한 유일한 트리는 스타 그래프(한 정점이 나머지 모든 정점과 연결된 형태)이며, 이 트리의 최대 매칭 크기는 1입니다.