Style change

Interview

Time limit2sMemory limit1024 MB

Summary

Convert each camelCase or CamelCase variable name to snake_case by lowercasing all letters and inserting an underscore before each capital letter.

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

Problem

Yellow needs to reboot his computer. He has a special reboot flash drive with a program on it. All variables in this program are written in CamelCase or camelCase. Yellow does not like this, and he wants every variable written in snake_case.

Both styles pack a phrase of several words into one string with no spaces. In camelCase (CamelCase), the first letter of each word in the phrase is capitalized, except that the first word may keep a lowercase first letter. All other letters stay lowercase, and the words are joined without spaces. In snake_case, all letters of the words are lowercase, and the words are separated by _.

Input

The first line contains one integer $n$ , the number of variable names whose style Yellow wants to change ( $1 \le n \le 100$ ). Each of the next $n$ lines contains a string $s\_i$ made of Latin letters, the variable name ( $1 \le |s\_i| \le 1\\,000$ ).

Output

Print each variable name converted to snake_case.

Examples1

Example 1

Input

4
camelCase
CamelCase
toBeOrNotToBe
ABCDE

Expected output

camel_case
camel_case
to_be_or_not_to_be
a_b_c_d_e