Yellow needs to complete the task of restarting the computer. He has a special reboot flash drive with the program. All variables in this program are written in CamelCase or camelCase style. Yellow is not happy with this and wants all variables to be written in the snake_case style.

Both of these styles are used to write a phrase of several words in a line without spaces. In camelCase (CamelCase) to do this, the first letter of every word in the phrase, except possibly the first, is capitalized, all other letters remain small, and then the words are written one after the other without spaces. In snake_case all letters of words are kept small and words are separated by "_".

Help Yellow convert some variable names from camelCase (CamelCase) to snake_case.

Input

The first line contains one integer n (1 ≤ n ≤ 100) - the number of variable names for which Yellow wants to change the style.

Then there are n lines si (1 ≤ |si| ≤ 1000), each of which consists of Latin letters - variable names.

Output

Print the name of each variable converted to snake_case.