Mixing Coins

英文題目敘述

Misaka likes to shoot coins as a powerful railgun.

She prepares a line of coins to fight crime. To produce a stronger coin, she mixes coins together. However, coins with different materials are not compatible to each other, so she only mixes coins with same material together.

Here's the steps Misaka makes coins:

Find first three consecutive coins with same material from the beginning of the line
Take them out from the line
Mix together and produce a new coin with same material
Put the new coin at the end of line

She repeatedly do these steps until she can't produce new coins anymore.

Misaka wants to know how many coins she will have. Please help her count coins rapidly!

英文輸入說明

On the first line there is a single integer $T$ indicating the number of test cases.

The first line of each test case contains an integer $N$ indicating the number of groups of consecutive coins Misaka has. All coins are in a single line.

Then $N$ lines follow, each line containing a character $c_i$ and an integer $n_i$, denoting that there are $n_i$ consecutive coins with material $c_i$ for $i$-th group of consecutive coins, behind $(i-1)$-th.

You may assume:

$T \leq 10$
$1 \leq N \leq 10^5$
$1 \leq n_i \leq 10^9$
$c_i$ is an uppercase alphabet, $c_i \neq c_{i+1}$ for $1 \leq i < N$

英文輸出說明

For each test case, output an integer in one line, indicating the number of coins after Misaka doing the steps of making coins as many as possible.

範例輸入

2
3
A 3
B 1
A 2
3
A 2
B 3
A 2

範例輸出

2
3

中文題目敘述

御坂喜歡用硬幣當作電磁炮射擊。

為了打擊犯罪，她準備了一排硬幣。為了生產出更強力的硬幣，她會把硬幣們混合在一起。然而，不同材質的硬幣之間並不相容，所以她只會將相同材質的硬幣混合。

以下是御坂製作硬幣的步驟：

從序列的頭開始，找出第一組連續三個相同材質的硬幣
將它們從序列取出
混合在一起，生產出一枚新的相同材質的硬幣
將新硬幣放回序列尾端

她會重複做這些步驟，直到她不能再生產新的硬幣。

御坂想要知道她最後會有多少硬幣。請趕快幫她計算硬幣吧！

中文輸入說明

第一行有一個整數 $T$ ，表示測試資料的數量。

每組測試資料的第一行有一個正整數 $N$，表示御坂有 $N$ 組連續的硬幣。所有硬幣都在一排之中。

接著有 $N$ 行，每一行有一個字元 $c_i$ 和正整數 $n_i$ ，表示第 $i$ 組有連續 $n_i$ 個材質為 $c_i$ 的硬幣，接在第 $(i-1)$ 組硬幣之後。

可假設：

$T \leq 10$
$1 \leq N \leq 10^5$
$1 \leq n_i \leq 10^9$
$c_i$ 是一個英文大寫字母，$c_i \neq c_{i+1}$ 對於 $1 \leq i < N$

中文輸出說明

對於每組測試資料，輸出一個整數於一行，表示御坂在做完盡量多次製作硬幣的步驟之後，有多少硬幣。

Judge Setting

run-time limit: 5000 ms
memory limit: 65536000 byte
測資數量: 0