Home

Contest: Task: Related: TaskB

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: SSTTST ⇒ STST ⇒ ST ⇒ ``.

Sample Input 3

TSSTTTSS

Sample Output 3

4

$X$ will become: TSSTTTSS ⇒ TSTTSS ⇒ TTSS.