String Imbalance

Bogdan is giving Carlo orthography lessons! The course will be held in $Q$ days, during which Carlo will have to copy the string written on the blackboard as an exercise. The string is initially empty, and each day $i$ ($0 \le i < Q$) will be extended by Bodgan with $F_i$ copies of the character $C_i$ that is the lesson's topic. More formally, the exercise string $S_i$ will be as follows:

• $S_0$ consists of $F_0$ characters equal to $C_0$;
• $S_i$ is the concatenation of $S_{i-1}$ and $F_i$ characters equal to $C_i$.

Carlo is very prone to mistakes and on day $i$ he will get up to $K_i$ letters wrong. Thus, the string he will write on that day will differ from $S_i$ in at most $K_i$ positions. Bogdan would like to know the minimum possible imbalance of the strings Carlo will write. We define the imbalance of a string of length $N$ as the number of pair of indices $(i, j)$ such that $0 \le i < j < N$ and $S_i \neq S_j$.

Input data

The first line of the input file contains a single integer $T$, the number of test cases. $T$ test cases follow, each preceded by an empty line. Each test case consists of:

• a line containing integer $Q$.
• $Q$ lines, the $i$-th of which consisting of integer $F_{i}$; character $C_{i}$ and integer $K_{i}$.

Output data

For each query from each testcase, output a single line containing one integer denoting the answer for that query.

Constraints and clarifications

• $1 \le T \le 10$.
• $1 \le Q \le 200 \ 000$.
• $1 \le F_i \le 5 \ 000$.
• $1 \le K_i \le 10^9$.
• $C_i$ is a lowercase or uppercase letter of the English alphabet.
• The sum of $Q$ over all test cases does not exceed $200 \ 000$.

Examples

stdin

2
3
2 a 0
3 b 3
2 c 2
2
2 A 10
3 a 1

stdout

0
0
10
0
4

Explanation

In the first testcase of the sample case:

• $S_0$ = aa. Its imbalance is $0$ and it is possible for Carlo to copy it correctly.
• $S_1$ = aabbb. It is possible for Carlo to write aaaaa, which has an imbalance of $0$.
• $S_2$ = aabbbcc. Its imbalance is $16$. It is possible for Carlo to write aabbbbb, which has an imbalance of $10$. He cannot write a string with a lower imbalance with up to $2$ mistakes.