题目描述

Lura 感到无聊，决定用五个字母 $\texttt{a}$、$\texttt{b}$、$\texttt{c}$、$\texttt{d}$、$\texttt{e}$ 创造一种简单的语言。该语言中有两类字母：

• 元音字母：$\texttt{a}$ 和 $\texttt{e}$，用 $\textsf{V}$ 表示。
• 辅音字母：$\texttt{b}$、$\texttt{c}$、$\texttt{d}$，用 $\textsf{C}$ 表示。

该语言中有两种音节类型：$\textsf{CV}$（辅音加元音）或 $\textsf{CVC}$（元音前后都有辅音）。例如，$\texttt{ba}$、$\texttt{ced}$、$\texttt{bab}$ 都是音节，但 $\texttt{aa}$、$\texttt{eda}$、$\texttt{baba}$ 不是。该语言中的一个单词由若干音节组成。Lura 已经写下了一个单词，但她不知道如何将其划分为音节。请你帮助她将单词划分为音节。

例如，给定单词 $\texttt{bacedbab}$，可以划分为 $\texttt{ba.ced.bab}$（点号 $\texttt{.}$ 表示音节分界）。

输入格式

输入包含多组测试数据。第一行包含一个整数 $t$（$1 \leq t \leq 100$），表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$），表示单词的长度。

每个测试用例的第二行包含一个长度为 $n$ 的字符串，仅由小写拉丁字母组成，表示该单词。

所有给定的单词都是该语言中的合法单词，即只包含 $\texttt{a}$、$\texttt{b}$、$\texttt{c}$、$\texttt{d}$、$\texttt{e}$ 这五个字母，并且每个单词都由若干音节组成。

所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个字符串，表示将单词按音节划分后，用点号 $\texttt{.}$ 分隔相邻音节的结果。

如果有多种划分方式，输出任意一种即可。输入保证至少存在一种合法划分。

样例

6
8
bacedbab
4
baba
13
daddecabeddad
3
dac
6
dacdac
22
dababbabababbabbababba

ba.ced.bab
ba.ba
dad.de.ca.bed.dad
dac
dac.dac
da.bab.ba.ba.bab.bab.ba.bab.ba

样例说明

由 ChatGPT 4.1 翻译

来源

Codeforces 1915D，英文题名 Unnatural Language Processing。