Problem Statement

Bob is bored and does not have anything to do, rather he does not have anything interesting to do. But he does have a huge list of assignments that he needs to complete. He is tired of looking at the same boring list again and again, so he decides to make this list more "funky".

According to Bob, a "funky string" is one that is composed of space separated "funky words". A "funky word" is one in which each character is alternatively upper case and lower case, that is, if the first character is uppercase, then the next one is lowercase and so on. However, Bob's definition of a "funky string" has the added constraint that all the odd numbered words start with a lowercase leter, whereas all even numbered words start with an uppercase letter ( where the words are numbered 1, 2.... n )

Also note that a string is composed of space separated words, such that two consecutive words have exactly one space in between them.

Examples:

(1) "bOb Is bOrEd" -> This is a valid funky string since each of the constituent words is funky, and only the odd numbered words start with a lowercase letter.

(2) "I aM BoReD tOo" -> Not funky, since the first word starts with an uppercase. The correct format would be "i Am bOrEd ToO"

Given a string of characters, please help Bob to convert this to a funky string.

Input

The first line contains a single integer T, denoting the number of test cases. ( 1<=T<=100 ). T lines of test cases follow.

The i^th test case consists of a single string, s_i ( 1<=|s_i| <= 1000 ) which you have to convert to a funky string. This string is guaranteed to consist of spaces, uppercase and lowercase characters only.

Output

For each test case, output on a single line the corresponding funky string.

Example

Input #1:
Programming is fun
 
Output #1:
pRoGrAmMiNg Is fUn


Input #2:
hahahaha

Output #2:
hAhAhAhA


Input #3:
i AM waiting FOR the WeeKEnd

Output #3: 
i Am wAiTiNg FoR tHe WeEkEnD