1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
// PA 2024 5C - migawka
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

long long t, n, a;
vector<long long> input;
long long sum, before, after, cand;
vector<long long> twos, threes;
#define MIL 1000000
//#define MIL 100

long long splitAlg2(long long pos, long long left, long long right) {
	long long mid = (left + right) / 2;
	//cout << "    split2 " << left << " " << mid << " " << right << endl;
	cand = before * (after - mid) * mid +
			before * twos[mid] + 
			(after - mid) * twos[mid] + 
			threes[mid];
	if (cand >= input[pos]) {
		if (left == right) {
			return left;
		}
		return splitAlg2(pos, left, mid);
	} else {
		if (left == right) {
			return -1;
		}
		return splitAlg2(pos, mid + 1, right); 
	}
}

bool testForNum(long long people) {
	before = 0;
	after = people;
	//cout << "  testing: " << people << endl;
	
	for (long long i = 0; i < n; ++i) {
		cand = splitAlg2(i, 0, after);
		//cout << "  cand " << cand << endl;
		if (cand < 0) {
			return false;
		}
		before += cand;
		after -= cand;
		if (after < 0) {
			return false;
		}
	}
	
	return true;
}

long long splitAlg(long long left, long long right) {
	//cout << "split " << left << " " << right << endl;
	if (left == right) {
		return left;
	}		
	
	long long mid = (left + right) / 2;
	if (testForNum(mid)) {
		return splitAlg(left, mid);
	} else {
		return splitAlg(mid + 1, right); 
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	
	twos.push_back(0);
	twos.push_back(0);
	twos.push_back(1);
	a = 1;
	for (long long i = 3; a <= 3 * MIL; ++i) {
		a = a * i / (i - 2);
		twos.push_back(a);
	}
	
	threes.push_back(0);
	threes.push_back(0);
	threes.push_back(0);
	threes.push_back(1);
	a = 1;
	for (long long i = 4; a <= 3 * MIL; ++i) {
		a = a * i / (i - 3);
		threes.push_back(a);
	}
	
	a = twos.size() - threes.size();
	for (long long i = 0; i < a; ++i) {
		threes.push_back(3 * MIL);
	}
	
	cin >> t;
	
	for (long long i = 0; i < t; ++i) {
		cin >> n;
		sum = 0;
		for (long long j = 0; j < n; ++j) {
			cin >> a;
			input.push_back(a);
			sum += a;
		}
		
		cout << splitAlg(0, 3 * sum) << endl;
		input.clear();
	}
	
	/*for (unsigned long long i = 0; i < twos.size(); ++i) {
		cout << twos[i] << " ";
	}
	cout << endl;
	for (unsigned long long i = 0; i < threes.size(); ++i) {
		cout << threes[i] << " ";
	}
	cout << endl;*/
	
	return 0;
}