#include <bits/stdc++.h>
using namespace std;

#define int long long
#define double long double

#define pii pair<int, int>

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
#ifdef CB
	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
#endif
	int T;
	cin >> T;
	while (T--) {
		int Q;
		cin >> Q;
		vector<int> c(150);
		for (int i = 0; i < Q; i++) {
			int F, K;
			char C;
			cin >> F >> C >> K;
			c[C] += F;
			vector<int> v;
			for (char j = 'A'; j <= 'z'; j++) {
				if (c[j]) {
					v.push_back(c[j]);
				}
			}
			sort(v.begin(), v.end());
			int j = 0;
			while (j < v.size() - 1 && v[j] <= K) {
				K -= v[j];
				v.back() += v[j];
				v[j] = 0;
				j++;
			}
			v.back() += K;
			v[j] -= K;
			int ans = 0;
			for (char j = 0; j < v.size(); j++) {
				for (char k = j + 1; k < v.size(); k++) {
					ans += v[j] * v[k];
				}
			}
			cout << ans << '\n';
		}
	}
	return 0;
}