﻿ AGC005 A - STring - Atcoder

Home

Score : $300$ points

Problem Statement

We have a string $X$, which has an even number of characters. Half the characters are S, and the other half are T.

Takahashi, who hates the string ST, will perform the following operation $10^{10000}$ times:

• Among the occurrences of ST in $X$ as (contiguous) substrings, remove the leftmost one. If there is no occurrence, do nothing.

Find the eventual length of $X$.

Constraints

• $2 ≦ |X| ≦ 200,000$
• The length of $X$ is even.
• Half the characters in $X$ are S, and the other half are T.

Partial Scores

• In test cases worth $200$ points, $|X| ≦ 200$.

Input

The input is given from Standard Input in the following format:

$X$


Output

Print the eventual length of $X$.

Sample Input 1

TSTTSS


Sample Output 1

4


In the $1$-st operation, the $2$-nd and $3$-rd characters of TSTTSS are removed. $X$ becomes TTSS, and since it does not contain ST anymore, nothing is done in the remaining $10^{10000}-1$ operations. Thus, the answer is $4$.

Sample Input 2

SSTTST


Sample Output 2

0


$X$ will eventually become an empty string: SSTTSTSTSTST ⇒ .

Sample Input 3

TSSTTTSS


Sample Output 3

4


$X$ will become: TSSTTTSSTSTTSSTTSS.