You are given a string, s, consisting only of the letters P, A, N and D.

You are going to delete some characters from that string to make a new string (but keep the order), you want to create a string with the highest POWER level!

The power level of the leftover string is x if you have exactly x of each character in PANDA in the exact order of the word PANDA.

For example:

Power level 0 is achieved with the empty string.

Power level 1 with a string PANDA

Power level 2 with a string PPAANNDDAA

Power level 3 with a string PPPAAANNNDDDAAA and so on.

More formally, to create a string with power levelx you must have exactly x copies of the character P, followed by x copies of the character A, then x copies of the character N, then x copies of the character D and finally x copies of the character A.

Output the maximum power level you can achieve by deleting characters from the given string.

Input

You first and only line will contain a single string s

The length of s will not exceed 100,000

Output

A single integer representing the maximum power level you can create.

Example

Input 1
PADPAPAAANDNDNPANDADDDAAADA

Output 1
3

Input 2
ADNAP

Output 2
0