Ashley decided that she will spend her Winter break reading Sci-Fi novels. However, one of the books that Ashley bought for her book marathon has a weird printing error: one of the pages does not have any spaces.
Ashley is not sure where the spaces should be, but she knows that English words never have ~4~ consonants or vowels (
u) in a row (such words would be thoroughly ridiculous). Can you help her find the minimum number of spaces required to break up the page into words such that each word might be valid?
The input begins with an integer ~N~ ~(1 \leq N \leq 500\ 000)~, the number of characters on the page. The next line contains a string ~S~ containing ~N~ characters. The characters are either upper or lower case letters.
For 30% of the cases, ~N \leq 20~.
For 60% of the cases, ~N \leq 1000~.
Output the minimum number of spaces required to split the sentence into words that may be valid.
Sample Input 1
Sample Output 1
Sample Input 2
Sample Output 2