You are given a string, which only consists of the letters P, A, N and D. In one operation, you can insert a letter somewhere into the string.

Determine the minimum number of insertions/operations so that if you cut the string into pieces, there is a possible cut so that all the pieces are either "DA" or "PAN".

Input

Your first and only line will contain the string (of length N, 1 <= N <= 1e5).

Output

Output a single integer representing the minimum number of insertions needed to be able to cut the string into substrings of only PAN and DA.

Example

Input 1:
PANDA

Output 1:
0

Input 2:
DPANA

Output 2:
2