An english word is given as input and it is modified using some format. Identify the format using the examples given below (examples given are sufficient to identify the format) and print the modified word as output.
STEWART is modified as EWARTSTAY, AMAR is modified as AMAR, MAN is modified as ANMAY etc.
Note: Input contains uppercase english words.
 
Example 1:
Input:
S = "GEEK"
Output:
EEKGAY
Explanation:
The string when modified gives "EEKGAY".
Example 2:
Input:
S = "ALL"
Output:
ALL
Explanation:
The string when modified remains the same.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function englishWords() which takes a String S as input and returns the modified String.
 
Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(|S|)
 
Constraints:
1 <= |S| <= 10^{5}

Difficulty: EASY
Tags: Mathematics
Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(|S|)

Starter code:
#User function Template for python3



class Solution:

    def englishWords(self, S):

        # code here 

Solutions:
class Solution:

	def englishWords(self, S):
		x = ['A', 'E', 'I', 'O', 'U']
		p = ''
		t = ''
		for i in S:
			if i not in x:
				p += i
			else:
				l = S.index(i)
				t = S[l:]
				break
		t += p
		if t == S:
			return S
		return t + 'AY'


class Solution:

	def englishWords(self, S):
		x = 'AEIOU'
		if S[0] in x:
			return S
		c = 0
		for i in S:
			if i in x:
				break
			c += 1
		r = S[c:]
		r = r + S[:c] + 'AY'
		return r


class Solution:

	def englishWords(self, s):
		v = ['A', 'E', 'I', 'O', 'U']
		ans = ''
		res = ''
		if s[0] in v:
			return s
		for i in range(len(s)):
			if s[i] not in v:
				res += s[i]
			elif s[i] in v:
				ans += s[i:]
				break
		ans += res
		ans += 'AY'
		return ans


class Solution:

	def englishWords(self, S):
		v = ['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U']
		l = list(S)
		k = ''
		p = []
		for i in range(len(l)):
			if l[i] not in v:
				k += l[i]
			else:
				p = l[i:]
				break
		if len(p) == len(l):
			return S
		p.append(k)
		p.append('AY')
		return ''.join(p)


class Solution:

	def englishWords(self, S):
		l = list(S)
		s = ''
		if l[0] in ['A', 'E', 'I', 'O', 'U']:
			return S
		else:
			for i in range(len(l)):
				if l[i] in ['A', 'E', 'I', 'O', 'U']:
					s += s.join(l[i:]) + s.join(l[:i]) + 'AY'
					break
		return s


class Solution:

	def englishWords(self, s):
		c = 0
		for i in range(len(s)):
			if s[i] not in 'AEIOU':
				c += 1
			else:
				break
		if c == 0:
			return s
		else:
			a = s[:c]
			b = s[c:]
			return b + a + 'AY'


class Solution:

	def englishWords(self, S):
		n = len(S)
		m = {'A', 'E', 'I', 'O', 'U'}
		if S[0] in m:
			return S
		for i in range(n):
			if S[i] in m:
				return S[i:] + S[:i] + 'AY'
		return ''


class Solution:

	def englishWords(self, S):
		z = ['A', 'E', 'I', 'O', 'U']
		l = ''
		m = ''
		for i in S:
			if i not in z:
				l += i
			else:
				k = S.index(i)
				m = S[k:]
				break
		m += l
		if m == S:
			return S
		return m + 'AY'


class Solution:

	def englishWords(self, S):
		v = ['A', 'E', 'I', 'O', 'U']
		a = ''
		b = ''
		for i in S:
			if i not in v:
				a += i
			else:
				l = S.index(i)
				t = S[l:]
				break
		t += a
		if t == S:
			return S
		return t + 'AY'


class Solution:

	def englishWords(self, S):
		vowel = ('A', 'E', 'I', 'O', 'U')
		if S.startswith(vowel):
			return S
		else:
			for (index, i) in enumerate(S):
				if i in vowel:
					return S[index:] + S[:index] + 'AY'


class Solution:

	def englishWords(self, S):
		newstr = ''
		oldstr = ''
		if S[0] == 'A' or S[0] == 'E' or S[0] == 'I' or (S[0] == 'O') or (S[0] == 'U'):
			return S
		else:
			for i in range(len(S)):
				if S[i] == 'A' or S[i] == 'E' or S[i] == 'I' or (S[i] == 'O') or (S[i] == 'U'):
					newstr += S[i:]
					oldstr += S[:i]
					break
			return newstr + oldstr + 'AY'


class Solution:

	def englishWords(self, S):
		if S[0] == 'A' or S[0] == 'E' or S[0] == 'I' or (S[0] == 'O') or (S[0] == 'U'):
			return S
		ans = ''
		for i in range(len(S)):
			if S[i] == 'A' or S[i] == 'E' or S[i] == 'I' or (S[i] == 'O') or (S[i] == 'U'):
				for j in range(i, len(S)):
					ans += S[j]
				for a in range(i):
					ans += S[a]
				break
		return ans + 'AY'


class Solution:

	def englishWords(self, S):
		x = ['A', 'E', 'I', 'O', 'U']
		p = ''
		t = ''
		for i in S:
			if i not in x:
				p = p + i
			else:
				l = S.index(i)
				t = S[l:]
				break
		t = t + p
		if t == S:
			return S
		return t + 'AY'
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		S = input()
		ob = Solution()
		print(ob.englishWords(S))


class Solution:

	def englishWords(self, S):
		index = -1
		for i in range(len(S)):
			if S[i] in ['A', 'E', 'I', 'O', 'U']:
				index = i
				break
		if index == 0:
			return S
		if index == -1:
			return S + 'AY'
		return S[index:] + S[0:index] + 'AY'