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

#ifdef DEBUG
ifstream in_file("minta/be1.txt");
#define input in_file
#define INTHENAMEOFGOD
#else
#define input cin
#define INTHENAMEOFGOD \
    ios::sync_with_stdio(0); \
    cin.tie(0); \
    cout.tie(0); 
#endif
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;

const int abc_num = ('z'-'a'+1)*2;
ll F, T, Q, len, K, num0, r, rollsum;
vector<ll> nums(abc_num, 0), nums_adj(abc_num, 0);
char C;

int ctoi(char c) {
    return (c >= 'a') ? ('Z'-'A'+1 + c-'a') : (c-'A');
}

int main() {
    INTHENAMEOFGOD
    input >> T;
    for (ll t = 0; t < T; t++) {
        input >> Q;
        len = 0;
        nums.assign(abc_num, 0);
        num0 = abc_num;
        for (ll q = 0; q < Q; q++) {
            input >> F >> C >> K;
            len += F;
            num0 -= nums[ctoi(C)] == 0;
            nums[ctoi(C)] += F;
            copy_n(nums.begin(), abc_num, nums_adj.begin());
            sort(nums_adj.begin(), nums_adj.end());
            ll &maxval = nums_adj.back();
            maxval += min(len-maxval, K);
            rollsum = r = 0;
            ll *i = &nums_adj[0]+num0;
            for (; i < &maxval; i++) {
                ll le = min(*i, K);
                K -= le;
                *i -= le;
                r += *i*(len-*i-rollsum);
                rollsum += *i;
            }
            r += maxval*(len-maxval-rollsum);
            cout << r << "\n";
        }
    }
}