Mixing Coins

Time limit5sMemory limit512 MB

Summary

Groups of equal coins are merged three at a time when three consecutive same-material coins appear, and the survivor count is requested.

Level: Medium7 of 10
Topics: Simulation, Stack, Implementation
Solved: No attempts yet

Problem

Misaka fires coins from a railgun. To fight crime she lays out a line of coins. A stronger coin comes from mixing coins together, and coins of different materials do not combine, so she only mixes coins of the same material.

She makes a coin like this.

Scanning from the front of the line, find the first position where three consecutive coins share a material.
Take those three coins out of the line.
Mix them into one new coin of the same material.
Put the new coin at the back of the line.

Misaka repeats these steps until she cannot make another coin.

Count the coins left in the line when she stops.

Input

The first line contains a single integer $T$ , the number of test cases.

The first line of each test case contains an integer $N$ , the number of groups of consecutive coins. All coins lie in a single line.

Each of the next $N$ lines contains a character $c_i$ and an integer $n_i$ , meaning that the $i$ -th group is $n_i$ consecutive coins of material $c_i$ and sits directly behind the $(i-1)$ -th group.

$1 \le T \le 10$
$1 \le N \le 10^5$
$1 \le n_i \le 10^9$
$c_i$ is an uppercase letter, and $c_i \ne c_{i+1}$ for every $i$ with $1 \le i < N$

Output

For each test case, print on one line the number of coins left when no new coin can be made.

Examples2

Example 1
Input
```
2
3
A 3
B 1
A 2
3
A 2
B 3
A 2
```
Expected output
```
2
3
```
Example 2
Input
```
4
1
A 1
1
A 2
1
A 3
1
Z 1
```
Expected output
```
1
2
1
1
```