Chef has a string S with him. Chef is happy if the string contains a contiguous substring of length strictly greater than 2 in which all its characters are vowels. 

Determine whether Chef is happy or not.

Note that, in english alphabet, vowels are a, e, i, o, and u.

------ Input Format ------ 

- First line will contain T, number of test cases. Then the test cases follow.
- Each test case contains of a single line of input, a string S.

------ Output Format ------ 

For each test case, if Chef is happy, print HAPPY else print SAD.

You may print each character of the string in uppercase or lowercase (for example, the strings hAppY, Happy, haPpY, and HAPPY will all be treated as identical).

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$3 ≤ |S| ≤ 1000$, where $|S|$ is the length of $S$.
$S$ will only contain lowercase English letters.

----- Sample Input 1 ------ 
4
aeiou
abxy
aebcdefghij
abcdeeafg

----- Sample Output 1 ------ 
Happy
Sad
Sad
Happy

----- explanation 1 ------ 
Test case $1$: Since the string aeiou is a contiguous substring and consists of all vowels and has a length $> 2$, Chef is happy.

Test case $2$: Since none of the contiguous substrings of the string consist of all vowels and have a length $> 2$, Chef is sad.

Test case $3$: Since none of the contiguous substrings of the string consist of all vowels and have a length $> 2$, Chef is sad.

Test case $4$: Since the string eea is a contiguous substring and consists of all vowels and has a length $> 2$, Chef is happy.

Difficulty: EASY
Tags: String algorithms

Data structures
Skill types: Data structures

Starter code:

Solutions:
T = int(input())
for i in range(T):
	S = input()
	vowels = ['a', 'e', 'i', 'o', 'u']
	a = []
	for i in range(len(S)):
		if S[i] in vowels and S[i + 1] in vowels and (S[i + 2] in vowels):
			a.append(1)
			break
	if len(a) == 1:
		print('Happy')
	else:
		print('Sad')


T = int(input())
for i in range(0, T):
	str = input()
	vowels = 'aeiou'
	flag = 0
	for i in range(0, len(str)):
		if str[i] in vowels and str[i + 1] in vowels and (str[i + 2] in vowels):
			flag = 1
			break
	if flag == 1:
		print('Happy')
	if flag == 0:
		print('Sad')


t = int(input())
for i in range(t):
	l = ['a', 'e', 'i', 'o', 'u']
	s = input()
	c = 0
	for j in range(len(s)):
		if s[j] in l:
			c = c + 1
		else:
			c = 0
		if c > 2:
			print('Happy')
			break
	if c <= 2:
		print('Sad')


t = int(input())
for i in range(t):
	S = input()
	count = 0
	flag = 0
	for i in range(len(S)):
		if S[i] in ['a', 'e', 'i', 'o', 'u']:
			count += 1
			if count > 2:
				flag = 1
		else:
			count = 0
	if flag:
		print('Happy')
	else:
		print('Sad')


for i in range(int(input())):
	s = input()
	a = 'Sad'
	for i in range(len(s) - 2):
		if s[i] in ['a', 'e', 'i', 'o', 'u']:
			if s[i + 1] in ['a', 'e', 'i', 'o', 'u']:
				if s[i + 2] in ['a', 'e', 'i', 'o', 'u']:
					a = 'Happy'
					break
	print(a)


n = int(input())
for i in range(n):
	s = input()
	c = 0
	v = ['a', 'e', 'i', 'o', 'u']
	for ele in s:
		if ele not in v:
			c = 0
		else:
			c += 1
			if c > 2:
				print('Happy')
				break
	if c < 2:
		print('Sad')


T = int(input())
VOWELS = ['a', 'e', 'i', 'o', 'u']
for tc in range(T):
	string = input()
	string = [x for x in string]
	for i in range(len(string) - 2):
		chefIsFeeling = 'Sad'
		x = i + 1
		y = i + 2
		if string[i] in VOWELS and string[x] in VOWELS and (string[y] in VOWELS):
			chefIsFeeling = 'Happy'
			break
	print(chefIsFeeling)


for i in range(int(input())):
	s = 'aeiou'
	l = input().lower()
	c = 0
	for i in range(len(l)):
		if l[i] in s:
			if l[i + 1] in s:
				if l[i + 2] in s:
					c = 3
					break
	if c > 2:
		print('Happy')
	else:
		print('Sad')


t = int(input())
for i in range(t):
	s = input()
	a = 'aeiou'
	c = 0
	k = 0
	for i in s:
		if i in a:
			c = c + 1
			if c == 3:
				k = 1
				break
		else:
			c = 0
	if k == 1:
		print('Happy')
	else:
		print('Sad')


for _ in range(int(input())):
	str_1 = input()
	vol_list = ['a', 'e', 'i', 'o', 'u']
	for i in range(0, len(str_1) - 2):
		if str_1[i] in vol_list:
			if str_1[i + 1] in vol_list and str_1[i + 2] in vol_list:
				print('Happy')
				break
	else:
		print('Sad')


for i in range(int(input())):
	a = list(input())
	l = ['a', 'e', 'i', 'o', 'u']
	m = 0
	for j in range(0, len(a) - 3):
		if a[j] in l and a[j + 1] in l and (a[j + 2] in l):
			m = 1
	if m == 1:
		print('Happy')
	else:
		print('Sad')


for t in range(int(input())):
	string = input()
	cou = 0
	result = 'Sad'
	for val in string:
		if val in 'aeiou':
			cou += 1
			if cou > 2:
				result = 'Happy'
				break
		else:
			cou = 0
	print(result)


t = int(input())
for p in range(t):
	x = input()
	a = 'Sad'
	for i in range(len(x) - 2):
		if x[i] in {'a', 'e', 'i', 'o', 'u'}:
			if x[i + 1] in {'a', 'e', 'i', 'o', 'u'}:
				if x[i + 2] in {'a', 'e', 'i', 'o', 'u'}:
					a = 'Happy'
					break
	print(a)


t = int(input())
for i in range(t):
	n = input()
	for j in range(len(n)):
		s = n[j:j + 3]
		c = 0
		for k in s:
			if k in ['a', 'e', 'i', 'o', 'u']:
				c += 1
		if c == 3:
			break
	if c == 3:
		print('Happy')
	else:
		print('Sad')


T = int(input())
vowels = ['a', 'e', 'i', 'o', 'u']
for i in range(T):
	s = input()
	count = 0
	res = False
	for i in s:
		if i in vowels:
			count += 1
			if count > 2:
				print('Happy')
				res = True
				break
		else:
			count = 0
	if res == False:
		print('Sad')


T = int(input())
for x in range(T):
	S = input()
	length = len(S)
	flag = 0
	i = 0
	while i < length - 2:
		if S[i] == 'a' or S[i] == 'e' or S[i] == 'i' or (S[i] == 'o') or (S[i] == 'u'):
			if S[i + 1] == 'a' or S[i + 1] == 'e' or S[i + 1] == 'i' or (S[i + 1] == 'o') or (S[i + 1] == 'u'):
				if S[i + 2] == 'a' or S[i + 2] == 'e' or S[i + 2] == 'i' or (S[i + 2] == 'o') or (S[i + 2] == 'u'):
					flag = 1
					break
		i = i + 1
	if flag == 1:
		print('Happy')
	else:
		print('Sad')


for i in range(int(input())):
	s = input()
	flag = 0
	l = ['a', 'e', 'i', 'o', 'u']
	for i in range(len(s) - 2):
		if s[i] in l and s[i + 1] in l and (s[i + 2] in l):
			flag = 1
			break
	if flag == 1:
		print('Happy')
	else:
		print('Sad')


def fun(s):
	c = 0
	for i in s:
		if i == 'a' or i == 'e' or i == 'i' or (i == 'o') or (i == 'u'):
			c = c + 1
		else:
			c = 0
		if c > 2:
			return 'Happy'
	return 'Sad'
for i in range(int(input())):
	s = input()
	print(fun(s))


n = int(input())
c = 0
for i in range(n):
	l = input()
	flag = False
	for i in range(0, len(l) - 2):
		if l[i] in 'aeiou':
			if l[i + 1] in 'aeiou':
				if l[i + 2] in 'aeiou':
					flag = True
	if flag == True:
		print('Happy')
	else:
		print('Sad')


t = int(input())
for i in range(t):
	s = input()
	str1 = 'aeiou'
	count = 0
	for j in s:
		if j in str1:
			count = count + 1
			if count > 2:
				break
		else:
			count = 0
	if count > 2:
		print('Happy')
	else:
		print('Sad')


for _ in range(int(input())):
	a = input()
	c = 'Sad'
	for i in range(len(a)):
		if a[i] in 'aeiou':
			if a[i + 1] in 'aeiou':
				if a[i + 2] in 'aeiou':
					c = 'Happy'
					break
	print(c)


t = int(input())
l = ['a', 'e', 'i', 'o', 'u']
for _ in range(t):
	s = input()
	for i in range(len(s) - 1):
		if s[i] in l:
			if s[i + 1] in l:
				if s[i + 2] in l:
					print('Happy')
					break
	else:
		print('Sad')


import re
regex = '[aeiou]{3,}'
for _ in range(int(input())):
	string = input()
	match = re.search(regex, string)
	if match == None:
		print('Sad')
	else:
		print('Happy')


n = int(input())
for i in range(n):
	s = input()
	d = list(s)
	p = ['a', 'e', 'i', 'o', 'u']
	c = 0
	flag = True
	for i in s:
		if i in p:
			c = c + 1
			if c == 3:
				flag = False
				print('Happy')
				break
		else:
			c = 0
	if c == 0:
		print('Sad')


t = int(input())
for i in range(t):
	x = str(input())
	y = 'aeiou'
	count = 0
	for i in range(len(x)):
		if x[i] in y:
			count += 1
			if count == 3:
				break
		else:
			count = 0
	if count > 2:
		print('Happy')
	else:
		print('Sad')


l = ['a', 'e', 'i', 'o', 'u']
for _ in range(int(input())):
	s = input()
	sub = ''
	for i in range(len(s)):
		if s[i] in l:
			sub = sub + s[i]
			if len(sub) > 2:
				print('Happy')
				break
		else:
			sub = ''
	if len(sub) == 0:
		print('Sad')


def solve(x):
	for i in range(len(x) - 2):
		if x[i] in 'aeiou' and x[i + 1] in 'aeiou' and (x[i + 2] in 'aeiou'):
			return 'Happy'
	return 'Sad'
n = int(input())
for i in range(n):
	x = input()
	print(solve(x))


n = int(input())
L = ['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U']
for i in range(n):
	x = 0
	s = input()
	for i in range(len(s) - 2):
		if s[i] in L and s[i + 1] in L and (s[i + 2] in L):
			print('Happy')
			x = 1
			break
	if x == 0:
		print('Sad')


m = int(input())
for j in range(0, m):
	a = {'a', 'e', 'i', 'o', 'u'}
	s = 0
	b = input()
	for i in range(len(b) - 2):
		if b[i] in a:
			if b[i + 1] in a:
				if b[i + 2] in a:
					s += 1
	if s > 0:
		print('Happy')
	else:
		print('Sad')


for _ in range(int(input())):
	s = input()
	cout = 0
	flag = 0
	for i in range(len(s)):
		if s[i] in ['a', 'e', 'i', 'o', 'u']:
			cout += 1
			if cout > 2:
				flag = 1
		else:
			cout = 0
	if flag == 1:
		print('Happy')
	else:
		print('Sad')


for _ in range(int(input())):
	s = input()
	l = ['a', 'e', 'i', 'o', 'u']
	cnt = 0
	for i in s:
		if i in l:
			cnt += 1
		elif cnt > 2:
			break
		else:
			cnt = 0
	if cnt > 2:
		print('Happy')
	else:
		print('Sad')


n = int(input())
for i in range(n):
	a = input()
	b = ['a', 'e', 'i', 'o', 'u']
	c = 0
	d = 0
	for i in a:
		if i in b:
			c += 1
			if c > 2:
				print('Happy')
				d = 1
				break
		else:
			c = 0
	if d == 0:
		print('Sad')


t = input()
for i in range(int(t)):
	s = input().lower()
	s = list(s)
	for i in range(len(s) - 2):
		check = 0
		if s[i] == 'a' or s[i] == 'e' or s[i] == 'i' or (s[i] == 'o') or (s[i] == 'u'):
			if s[i + 1] == 'a' or s[i + 1] == 'e' or s[i + 1] == 'i' or (s[i + 1] == 'o') or (s[i + 1] == 'u'):
				if s[i + 2] == 'a' or s[i + 2] == 'e' or s[i + 2] == 'i' or (s[i + 2] == 'o') or (s[i + 2] == 'u'):
					check = -1
					break
	if check == -1:
		print('Happy')
	else:
		print('Sad')


t = int(input())
for i in range(t):
	s = input()
	c = 0
	streak = 0
	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'):
			streak += 1
		else:
			streak = 0
		c = max(c, streak)
	if c > 2:
		print('Happy')
	else:
		print('Sad')