L. League of Letters
time limit per test
1 second
memory limit per test
64 megabytes
input
standard input
output
standard output

P, D, A, and O are warriors from different tribes. The warriors are vicious, hateful people who attack each other frequently. The warriors stand in a line and form leagues to avoid wars between tribes. A league is formed by removing several warriors (possibly zero) from the beginning and the end of the line. And a league is said to be safe if it has an equal number of warriors from each tribe.

For example, for warriors PDAOPDAOOPDA, PDAOPDAO, PDAO, DAOP, AOPD and OPDA is a league, but PDAOPDAOPDAO is not a league since it is not a substring of PDAOPDAOOPDA.

Given a line of warriors, find a safe league with the most warriors.

Input

A string $$$S$$$ of length $$$N$$$($$$1 \le N \le 2 \times 10^5 $$$), representing the line of warriors.

Output

Output an integer that represents the length of the safe league with the most warriors (i.e. a substring containing the same number of letters P, D, A, and O). If such league does not exist, output 0.

Examples
Input
PDAOPDAOOPDA
Output
12
Input
PPPOOPPOOAAAADDDDO
Output
16
Note

In the first example, the safe league with the most warriors is PDAOPDAOOPDA, so the output is $$$12$$$.

In the second example, the safe league with the most warriors is PPOOPPOOAAAADDDD, so the output is $$$16$$$.