Design a program to take a word as an input, and then encode it into a Pig Latin. A Pig Latin is an encrypted word in English, which is generated by doing following alterations:

The first vowel occurring in the input word is placed at the start of the new word along with the remaining alphabets of it. The alphabets present before the first vowel are shifted at the end of the new word followed by “ay”

Input

• First line of input is an integer T, which specifies number of test cases
• A string S that will be translated to Pig Latin

Constraints

• 1<= T <= 10000
• 1<= S <= 1000 in length