Description

众所周知，驼峰命名法是一种程序员广泛使用的变量命名方式。本题中的驼峰命名法定义如下：当变量名或函数名是由一个或多个单词连结在一起构成的唯一识别字时，每个单词的首字母都采用大写字母。如 $\texttt{MyName}, \texttt{MyAge}$。

卷王杨神则根据驼峰命名法发明了新的驼腚命名法，与驼峰命名法唯一不同的是，它的每个单词的末尾字母都采用大写字母，如 $\texttt{mYnamE, mYagE}$。

由于蒟蒻 jbgg 非常膜拜杨神，他想写一个将驼峰命名法转成驼腚命名法的程序，但 jbgg 对编程一窍不通，所以他来向你求助了！你能帮帮 jbgg 吗？

Format

Input

第一行一个正整数 $T(1 \leqslant T \leqslant 2 \times 10^5)$，表示有 $T$ 组数据。

接下来 $T$ 行，每行一个字符串 $s$。

保证所有的字符串 $s$ 中仅包含大写和小写英文字母，且首个字符为大写字母。

$1 \leqslant \sum |s| \leqslant 2 \times 10 ^ 5$，其中 $|s|$ 为字符串 $s$ 的长度。

Output

应输出 $T$ 行。对于每组数据输出一行符合驼腚命名法格式的字符串。

Samples

2
CrazyThursdayVMeFifty
DoNotPlayOverwatch

crazYthursdaYVmEfiftY
dOnoTplaYoverwatcH

2
OOOOOHhhhhhhh
LEEROYJEEEEEEENKIIIIIIIIIIIIIIINS

OOOOOhhhhhhhH
LEEROYJEEEEEEENKIIIIIIIIIIIIIIINS

Limitation

1s, 1024KiB for each test case.