你会得到一个长度为 $n$ 的字符串，这个字符串仅有两个字符：$A$ 和 $P$ 。

正如 $PPAP$ 一样，$P$ 和 $P$ 可以合并在一起，$A$ 和 $P$ 也能合并在一起，因此你可以一直做如下操作：

1. 删除一个子串 $PP$ ；
2. 删除一个子串 $AP$ 。

（子串的通俗解释是，字符串中的连续字符）

删除之后的字符串会重新拼接在一起，并且可以继续删除。

例如：$AAP\underline{AP}PA \rightarrow AA\underline{PP}A \rightarrow AAA$ 。

当然还有一种更优的删除方法：$A\underline{AP}APPA \rightarrow A\underline{AP}PA \rightarrow \underline{AP}A \rightarrow A$。

现在给定一个字符串，请问每个字符串经过若干次操作之后，最短的字符串的长度是多少。

输入格式

输入只有一行，包含一个长度为 $n$ 的、仅包含 $A$ 和 $P$ 的字符串。

输出格式

输出一个数字，表示经过删除后最短的字符串的长度。

样例

输入

AAPAPPA

输出

1

数据范围

$30\%$ 的数据满足 $1 \le n \le 4$ ；

$60\%$ 的数据满足 $1 \le n \le 10$ ；

$100\%$ 的数据满足 $1 \le n \le 10000$。