#include <cstdio>#include <cstdlib>#include <cmath>#include <set>#include <stack>#include <vector>#include <sstream>#include <cstring>#include <string>#include <map>#include <queue>#include <algorithm>#include <iostream>#define FFI freopen("in.txt", "r", stdin)#define maxn 1010#define INF 0x3f3f3f3f#define inf 1000000000#define mod 1000000007#define ULL unsigned long long#define LL long long#define _setm(houge) memset(houge, INF, sizeof(houge))#define _setf(houge) memset(houge, -1, sizeof(houge))#define _clear(houge) memset(houge, 0, sizeof(houge))using namespace std;const int N = (1<<20)+5;const int M = 30;int n;priority_queue <int> Q;int main () {	// FFI;	int t;	scanf("%d", &t);	while (t--) {		scanf("%d", &n);		for(int i = 0; i < n; ++ i) {			int a;			scanf("%d", &a);			Q.push(a);		}		if(n == 1) {			printf("%d\n", Q.top());			Q.pop();			continue;		}		int ans = 0;		while(!Q.empty()) {			int a = Q.top();			Q.pop();			int b = Q.top();			Q.pop();			if(Q.empty()) {				ans += a+1;				break;			}			ans += b;			Q.push(a-b+1);		}		printf("%d\n", ans);	}	return 0;}