동전 합치기

미사카는 동전을 레일건 탄환으로 쓴다. 범죄에 맞서려고 동전을 한 줄로 늘어놓았다. 더 강한 동전을 만들려면 동전을 합쳐야 하는데, 재질이 다른 동전끼리는 합쳐지지 않으므로 같은 재질끼리만 합친다.

동전을 만드는 순서는 다음과 같다.

1. 줄의 앞에서부터 살펴보며 같은 재질의 동전이 세 개 연속으로 놓인 첫 자리를 찾는다.
2. 그 세 개를 줄에서 빼낸다.
3. 세 개를 합쳐 같은 재질의 새 동전 한 개를 만든다.
4. 새 동전을 줄의 맨 뒤에 놓는다.

미사카는 새 동전을 더 만들 수 없을 때까지 이 순서를 반복한다.

반복이 끝났을 때 줄에 남은 동전의 개수를 구하라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스의 첫째 줄에는 연속한 동전 묶음의 개수 $N$이 주어진다. 모든 동전은 한 줄로 놓여 있다.

이어지는 $N$개의 줄에는 문자 $c_i$와 정수 $n_i$가 주어진다. $i$번째 묶음은 재질이 $c_i$인 동전 $n_i$개가 연속으로 놓인 것이고, $i-1$번째 묶음 바로 뒤에 있다.

• $1 \le T \le 10$
• $1 \le N \le 10^5$
• $1 \le n_i \le 10^9$
• $c_i$는 알파벳 대문자이고, $1 \le i < N$인 모든 $i$에 대하여 $c_i \ne c_{i+1}$이다.

각 테스트 케이스마다 새 동전을 더 만들 수 없을 때 줄에 남은 동전의 개수를 한 줄에 출력한다.