A string S is called *Chef's favourite* if every substring chef in S must have a substring code before it.

You are given a string S of size N that contains both code and chef as a substring. Please determine if S is Chef's favourite.

Note: A substring is a continuous part of string which can be obtained by deleting some (may be none) character's from the beginning and some (may be none) character's from the end.

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

- The first line of the input contains an integer T - the number of test cases. The test cases then follow.
- The first line of each test contains an integer N - the size of the string.
- The second line of each test contains a string S.

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

For each test case, output on a single line AC if S is Chef's favourite, or WA otherwise.

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

$1 ≤ T ≤ 10$
$1 ≤ N ≤ 10^{4}$
$|S| = N$
$S$ consists only of lowercase English characters
- Both code and chef appear as a substring at least once in $S$

----- Sample Input 1 ------ 
4
8
codechef
8
chefcode
14
sxycodeghychef
21
sxychefvsvcodehghchef

----- Sample Output 1 ------ 
AC
WA
AC
WA

----- explanation 1 ------ 
- Test case $1$: Substring code is present before chef.
- Test case $2$: Substring code is not present before chef.
- Test case $3$: Substring code is present before chef.
- Test case $4$: There is no code substring present before the first occurrence of chef.

Difficulty: EASY
Tags: String algorithms

Constructive algorithms

Data structures

Ad-hoc
Skill types: Data structures

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	s = input()
	k = s.find('chef', 0, n)
	y = s.find('code', 0, k)
	if y >= 0:
		print('AC')
	else:
		print('WA')


for i in range(int(input())):
	l = int(input())
	s = input()
	x = s.split('chef')
	if 'code' in x[0]:
		print('AC')
	else:
		print('WA')


for _ in range(int(input())):
	n = int(input())
	s = input()
	if s.index('code') < s.index('chef'):
		print('AC')
	else:
		print('WA')


for i in range(int(input())):
	n = int(input())
	s = input()
	r = ''
	for i in range(n - 3):
		if s[i:i + 4] == 'code':
			r = r + '0'
		elif s[i:i + 4] == 'chef':
			r = r + '1'
	i1 = r.index('0')
	i2 = r.index('1')
	if i1 < i2:
		print('AC')
	else:
		print('WA')


t = int(input())
for i in range(t):
	n = int(input())
	string = input()
	if 'code' in string and 'chef' in string:
		if string.index('code') < string.index('chef'):
			print('AC')
		else:
			print('WA')
	else:
		print('WA')


for _ in range(int(input())):
	n = int(input())
	s = input()
	for i in range(len(s)):
		d = s[i:i + 4]
		if d == 'code':
			print('AC')
			break
		elif d == 'chef':
			print('WA')
			break


q = int(input())
while q > 0:
	n = int(input())
	s = input()
	flag = 0
	ci = s.find('code')
	chi = s.find('chef')
	if ci == -1 or chi == -1:
		flag = 0
	elif ci < chi:
		flag = 1
	if flag == 1:
		print('AC')
	elif flag == 0:
		print('WA')
	q = q - 1


for i in range(int(input())):
	n = int(input())
	s = input()
	if 'code' in s and 'chef' in s:
		if s.index('code') < s.index('chef'):
			print('AC')
		else:
			print('WA')
	else:
		print('WA')


for _ in range(int(input())):
	n = int(input())
	l = input()
	code = l.find('code')
	chef = l.find('chef')
	if chef > code:
		print('AC')
	else:
		print('WA')


import re
for t in range(int(input())):
	l = input()
	s = input()
	code_pos = re.search('code', s).start()
	chef_pos = re.search('chef', s).start()
	if code_pos < chef_pos:
		print('AC')
	else:
		print('WA')


t = int(input())
for ni in range(t):
	n = int(input())
	s = input()
	if 'code' in s:
		if s.index('code') < s.index('chef'):
			print('AC')
		else:
			print('WA')
	else:
		print('WA')


t = int(input())
for t in range(t):
	n = int(input())
	s = input()
	i = s.find('code')
	j = s.find('chef')
	if i < j:
		print('AC')
	else:
		print('WA')


t = int(input())
for i in range(t):
	n = int(input())
	s = str(input())
	if s.index('code') < s.index('chef'):
		print('AC')
	else:
		print('WA')


T = int(input())
for i in range(T):
	N = int(input())
	S = input()
	p1 = S.find('code')
	p2 = S.find('chef')
	if p2 < p1:
		print('WA')
	elif 'code' in S:
		p = S.find('code')
		S = S[p:]
		if 'chef' in S:
			print('AC')
		else:
			print('WA')


t = int(input().strip())
while t > 0:
	l = int(input())
	s = input().strip()
	if s.find('code') < s.find('chef'):
		print('AC')
	else:
		print('WA')
	t = t - 1


for _ in range(int(input())):
	n = int(input())
	s = input()
	if 'code' in s and 'chef' in s:
		if s.find('code') < s.find('chef'):
			print('AC')
		else:
			print('WA')
	else:
		print('WA')


testcases = int(input())
for i in range(testcases):
	n = int(input())
	data = str(input())
	if data.index('code') < data.index('chef'):
		print('AC')
	else:
		print('WA')


n = int(input())
for i in range(0, n):
	m = int(input())
	k = input()
	if k.index('code') < k.index('chef'):
		print('AC')
	else:
		print('WA')


for _ in range(int(input())):
	n = int(input())
	s = input()
	for i in range(n - 3):
		if s[i:i + 4] == 'chef':
			if 'code' not in s[:i]:
				print('WA')
				break
	else:
		print('AC')


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	lis = []
	for i in range(len(s)):
		m = s[i:i + 4]
		lis.append(m)
	if 'code' in lis and 'chef' in lis and (lis.index('code') < lis.index('chef')):
		print('AC')
	else:
		print('WA')


for _ in range(int(input())):
	n = int(input())
	s = input()
	if s.count('code') == 0 or s.count('chef') == 0:
		ans = 'WA'
	else:
		s = s.replace('code', '@')
		s = s.replace('chef', '#')
		if s.index('@') < s.index('#'):
			ans = 'AC'
		else:
			ans = 'WA'
	print(ans)


a = int(input())
for i in range(a):
	b = int(input())
	c = input()
	d = c.find('code')
	e = c.find('chef')
	if d < e:
		print('AC')
	else:
		print('WA')


for numeroCasosPrueba in range(int(input())):
	tamañoCuerda = int(input())
	cadena = input()
	subcadena = cadena.find('code')
	subcadena1 = cadena.find('chef')
	if subcadena1 < subcadena:
		print('WA')
	else:
		print('AC')


for _ in range(int(input())):
	n = int(input())
	s = input()
	cdp = s.find('code')
	chp = s.find('chef')
	if chp < cdp:
		print('WA')
	else:
		print('AC')


import re
for tc in range(int(input())):
	n = int(input())
	s = input().strip()
	a = re.search('code', s)
	b = re.search('chef', s)
	if a and b:
		if a.start() < b.start():
			print('AC')
		else:
			print('WA')
	else:
		print('WA')


for _ in range(int(input())):
	n = int(input())
	s = input()
	i = 0
	flag = 1
	while i < len(s):
		if s[i] == 'c':
			if i + 3 < len(s) and s[i:i + 4] == 'code':
				i = i + 4
				while i < len(s):
					if s[i] == 'c':
						if i + 3 < len(s) and s[i:i + 4] == 'chef':
							print('AC')
							flag = 0
							break
					i += 1
				if flag == 0:
					break
			elif i + 3 < len(s) and s[i:i + 4] == 'chef':
				print('WA')
				break
		i += 1


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	res = s.find('code')
	l = s.find('chef')
	if res < l:
		print('AC')
	else:
		print('WA')


for i in range(int(input())):
	n = int(input())
	s = input()
	a = s.index('chef')
	b = s.index('code')
	if a > b:
		print('AC')
	else:
		print('WA')


for t in range(int(input())):
	n = int(input())
	s = input()
	k1 = s.index('code')
	k2 = s.index('chef')
	if k1 < k2:
		print('AC')
	else:
		print('WA')


from re import search
for _ in range(int(input())):
	n = int(input())
	s = input()
	if search('code', s).span()[0] < search('chef', s).span()[0]:
		print('AC')
	else:
		print('WA')


for _ in range(int(input())):
	a = int(input())
	b = input()
	c = b.index('code')
	d = b.index('chef')
	if c > d:
		print('WA')
	else:
		print('AC')


def r2(num):
	return range(1, num + 1)
ii = lambda : int(input())
li = lambda : list(map(int, input().split()))
si = lambda : input()
ssi = lambda : list(input())
sepi = lambda : map(int, input().split())
seti = lambda : set(map(int, input().split()))
for i in range(int(input())):
	lenOfStr = ii()
	term = si()
	ans = ''
	for i in range(lenOfStr - 3):
		if term[i:i + 4] == 'chef':
			ans = 'WA'
			break
		elif term[i:i + 4] == 'code':
			ans = 'AC'
			break
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	s = str(input())
	ans = ''
	for j in range(len(s) - 3):
		if s[j:j + 4] == 'chef':
			ans = 'WA'
			break
		elif s[j:j + 4] == 'code':
			ans = 'AC'
			break
	print(ans)


for i in range(int(input())):
	n = int(input())
	s = input()
	cd = s.index('code')
	cf = s.index('chef')
	if cd < cf:
		print('AC')
	else:
		print('WA')


for _ in range(int(input())):
	n = int(input())
	s = input()
	a = s.split('chef')
	if 'code' in a[0]:
		print('AC')
	else:
		print('WA')


n = int(input())
for i in range(0, n):
	size = int(input())
	string = input()
	if string.index('code') < string.index('chef'):
		print('AC')
	else:
		print('WA')


for _ in range(int(input())):
	(N, s) = (int(input()), input())
	idx_code = s.index('code')
	idx_chef = s.index('chef')
	if idx_chef < idx_code:
		print('WA')
	else:
		print('AC')


for t in range(int(input())):
	n = int(input())
	s = input()
	k = s.find('chef')
	if 'code' in s[:k]:
		print('AC')
	else:
		print('WA')


for x in range(int(input())):
	n = int(input())
	a = input()
	co = a.index('code')
	ch = a.index('chef')
	if co > ch:
		print('WA')
	elif ch >= co + 4:
		print('AC')
	else:
		print('WA')


s = int(input())
for i in range(0, s, 1):
	n = int(input())
	st = input()
	if st.index('code') < st.index('chef'):
		print('AC')
	else:
		print('WA')


for _ in range(int(input())):
	s = int(input())
	p = input()
	x = p.index('chef')
	y = p.index('code')
	if y < x:
		print('AC')
	else:
		print('WA')


def find_chef(s, lb, ub):
	for i in range(ub):
		if s[i:i + 4] == 'chef':
			return 1
	return 0
for _ in range(int(input())):
	n = int(input())
	s1 = input()
	for i in range(0, n - 3):
		if s1[i:i + 4] == 'chef':
			print('WA')
			break
		if s1[i:i + 4] == 'code':
			if find_chef(s1, i + 5, n - 3) == 1:
				print('AC')
				break


n = int(input())
while n > 0:
	k = int(input())
	s = input()
	x = s.replace('code', 'A')
	y = x.replace('chef', 'B')
	if y.index('A') < y.index('B'):
		print('AC')
	else:
		print('WA')
	n -= 1


for t in range(int(input())):
	N = int(input())
	s = input()
	x = s.replace('code', 'A')
	y = x.replace('chef', 'B')
	if y.index('A') < y.index('B'):
		print('AC')
	else:
		print('WA')


t = int(input())
for i in range(0, t):
	n = int(input())
	s = input()
	for i in range(0, len(s)):
		if s[i:i + 4] == 'code':
			print('AC')
			break
		elif s[i:i + 4] == 'chef':
			print('WA')
			break


for x in range(int(input())):
	n = int(input())
	s = input()
	if 'code' in s and 'chef' in s:
		co = s.index('code')
		ch = s.index('chef')
		if co < ch:
			print('AC')
		else:
			print('WA')
	else:
		print('WA')


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	a = 0
	b = s.find('chef')
	for j in range(s.count('chef')):
		if s.find('code') > b:
			a = 1
			break
		b = s.find('chef', b + 1)
	if a == 0:
		print('AC')
	else:
		print('WA')


t = int(input())
for i in range(0, t):
	n = int(input())
	s = input()
	ans = s.find('chef')
	s = s[:ans]
	if s.find('code') != -1:
		print('AC')
	else:
		print('WA')


t = int(input())
while t:
	n = int(input())
	s = input()
	try:
		a = s.index('chef')
	except:
		a = n + 5
	try:
		b = s.index('code')
	except:
		b = n + 5
	if a < b:
		print('WA')
	else:
		print('AC')
	t -= 1


T = int(input())
for _ in range(T):
	N = int(input())
	S = input()
	if 'chef' in S:
		ind = S.find('chef')
		if 'code' in S[:ind]:
			print('AC')
		else:
			print('WA')


t = int(input())
for i in range(t):
	N = int(input())
	S = input()
	for i in range(0, len(S)):
		if S[i] == 'c' and S[i + 1] == 'o' and (S[i + 2] == 'd') and (S[i + 3] == 'e'):
			print('AC')
			break
		if S[i] == 'c' and S[i + 1] == 'h' and (S[i + 2] == 'e') and (S[i + 3] == 'f'):
			print('WA')
			break


t = int(input())
for i in range(t):
	N = int(input())
	S = input()
	a = S.find('chef')
	b = S[:a]
	if 'code' in b:
		print('AC')
	else:
		print('WA')


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	x = s.find('code')
	y = s.find('chef')
	if x == -1 or y == -1:
		print('WA')
	elif x < y:
		print('AC')
	else:
		print('WA')