On the Planet Ivoril

Interview

Time limit2sMemory limit1024 MB

Summary

Each word must become an alternating noun or an all-vowel verb; find the fewest character changes needed across all words.

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

Statement

The people of Ivoril all speak the Ivoril language. It is very easy to learn. It has only nouns and verbs, and they can be combined in any order. A noun is a string where vowels and consonants alternate. A verb is a string made only of vowels. Every such string is a word. Ivoril speakers use only lowercase Latin letters. The vowels are a, e, i, o, u, and y. All other letters are consonants.

Young Kugona started an internship at the popular Ivoril newspaper Namenu iou. She was given a job nobody else wanted: checking finished text for spelling mistakes. She wants to finish quickly, so she plans to change as few characters as possible. Write a program that automates this check.

Each word must be changed into a valid noun or a valid verb. Find the minimum total number of characters that must be changed.

Input

The first line contains one integer $N$ , the number of words in the text $(1 \le N \le 10^5)$ . The second line contains $N$ words $s_i$ separated by spaces $(1 \le |s_i| \le 10^6)$ . The total length of all words does not exceed $10^6$ .

Output

Print one integer, the minimum number of spelling errors in the text.

Examples2

Example 1
Input
```
3
augaa feeer evtry
```
Expected output
```
3
```
Example 2
Input
```
4
naumen is the best
```
Expected output
```
4
```