Keyboard Typo

Time limit2sMemory limit128 MB

Summary

Simulate 2-beolsik Korean keyboard input composition rules to find the position of the first character that breaks valid syllable formation.

Level: Medium6 of 10
Topics: Simulation, Implementation, String
Solved: No attempts yet

Problem

When typing Korean on a computer, a key sequence can be written as the English letters printed on a standard 2-beolsik Korean keyboard. Given such a string, scan it from left to right and check whether it can still be composed into Korean syllables by the standard 2-beolsik composition rules. If reading a character makes composition impossible, that character's position is the first typo. If the string ends while the last syllable has only an initial consonant and is not complete, the position of that initial consonant is the first typo.

Input

The first line contains the typed string. Each character is an English letter representing a key on a 2-beolsik Korean keyboard.

Output

Print the 1-based position of the first typo. If there is no typo, print 0.

Examples4

Example 1
Input
```
Wkwmdskkdy
```
Expected output
```
8
```
Example 2
Input
```
qnpfr
```
Expected output
```
0
```
Example 3
Input
```
wwhrysladk
```
Expected output
```
2
```
Example 4
Input
```
shrkekanswp
```
Expected output
```
0
```