CF1915D Unnatural Language Processing

Lura was bored and decided to make a simple language using the five letters $ \texttt{a} $ , $ \texttt{b} $ , $ \texttt{c} $ , $ \texttt{d} $ , $ \texttt{e} $ . There are two types of letters: - vowels — the letters $ \texttt{a} $ and $ \texttt{e} $ . They are represented by $ \textsf{V} $ . - consonants — the letters $ \texttt{b} $ , $ \texttt{c} $ , and $ \texttt{d} $ . They are represented by $ \textsf{C} $ . There are two types of syllables in the language: $ \textsf{CV} $ (consonant followed by vowel) or $ \textsf{CVC} $ (vowel with consonant before and after). For example, $ \texttt{ba} $ , $ \texttt{ced} $ , $ \texttt{bab} $ are syllables, but $ \texttt{aa} $ , $ \texttt{eda} $ , $ \texttt{baba} $ are not.A word in the language is a sequence of syllables. Lura has written a word in the language, but she doesn't know how to split it into syllables. Help her break the word into syllables. For example, given the word $ \texttt{bacedbab} $ , it would be split into syllables as $ \texttt{ba.ced.bab} $ (the dot $ \texttt{.} $ represents a syllable boundary).

The input consists of multiple test cases. The first line contains an integer $ t $ ( $ 1 \leq t \leq 100 $ ) — the number of test cases. The description of the test cases follows. The first line of each test case contains an integer $ n $ ( $ 1 \leq n \leq 2 \cdot 10^5 $ ) — the length of the word. The second line of each test case contains a string consisting of $ n $ lowercase Latin characters — the word. All words given are valid words in the language; that is, they only use the letters $ \texttt{a} $ , $ \texttt{b} $ , $ \texttt{c} $ , $ \texttt{d} $ , $ \texttt{e} $ , and each word is made up of several syllables. The sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

For test case, output a string denoting the word split into syllables by inserting a dot $ \texttt{.} $ between every pair of adjacent syllables. If there are multiple possible splittings, output any of them. The input is given in such a way that at least one possible splitting exists.