string-division

Kevin has a string S consisting of N lowercase English letters.  

Kevin wants to split it into 4 pairwise different non-empty parts.  For example, string "happynewyear" can be splitted into "happy", "new", "ye" and "ar". He can't delete any characters or change the order of the characters.

Help Kevin and find if there exist at least one possible spliting.

Input format:

The first line of input will contain an integer T, denoting the number of test cases. Each of the next T lines contains a string S.

Output format:

For every test case output "YES" if it is possible to split the string and "NO" otherwise.

Constraints:
1 ≤ T ≤ 100
1 ≤ N ≤ 1000
N ≤ 20 in test data worth 40% of all points

SAMPLE INPUT
2
ababca
aaabb

SAMPLE OUTPUT
YES
NO

Source: hackerearth | Difficulty: EASY
Tags: Fundamentals

Complete search


Solutions:
'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''

def get_ans(string):
	
	if len(string) < 4:
		return "NO"
	
	if len(string) >= 10:
		return "YES"
		
	if len(string) == 4:
		for i in range(len(string)):
			if string.count(string[i]) != 1 :
				return "NO"
		return "YES"
		
	else:

		# if len(g) >= 4 or len(ng) >= 4:
		# 	return "YES"
		# else:
		dd = dict((x, string.count(x)) for x in string)
		if len(dd) == 4:
			return "YES" 
		elif len(dd) == 2 and len(string) < 7:
			return "NO"

		ln = len(string)
		if ln % 2 == 0:
			if string[:ln/2] != string[ln/2:]:
				return "YES"
			else:
				return "NO"

		else:
			if string[:ln/2] != string[ln/2+1:]:
				return "YES"
			else:
				if string[ln/2] not in string[:ln/2] and len(string[:ln/2]) != 2:
					return "YES"
				else:
					return "NO"
'''
		if string[0] != string[1] and string[0] != string[2] and string[1] != string[2]:
			return "YES"

		if string[-1] != string[-2] and string[-1] != string[-3] and string[-2] != string[-3]:
			return "YES"

		dd = dict((x, string.count(x)) for x in string)
		if len(dd) == 4:
			return "YES" 
		elif len(dd) == 2 and len(string) < 7:
			return ""

		g = [] 
		ng = []
		ns = ''
		s = ''
		for i in range(len(string)):
			s += string[i]
			ns += string[len(string)-i-1]
			if s not in g:
				g.append(s)
				s = ''
				
			if ns not in ng:
				ng.append(ns)
				ns = ''
				
		if len(g) >= 4 or len(ng) >= 4:
			return "YES"
		else:
			if len(string) % 2 == 0:

			else:
'''
					
'''
f = open("ipp.txt","r")

lns = f.readlines()

for i in range(1,len(lns)):
	lns[i] = lns[i][:len(lns[i])-1]
	print lns[i][:11],len(lns[i]),get_ans(lns[i])
	# s = raw_input()

exit()
'''
n = int(input())

for i in range(n):
	print(get_ans(input()))
# '''
	


T = eval(input())
for i in range(T):
	string = input()
	l = len(string)
	ls = len(set(string))
	if l < 4:
		print('NO')
	elif l > 9:
		print('YES')
	elif l == 4 and ls > 3:
		print('YES')
	elif l > 4 and ls > 2:
		print('YES')
	elif l > 6 and ls > 1:
		print('YES')
	else:
		print('NO')
	


t=eval(input())

while(t>0):
	s=input();
	flag1=0
	flag2=0
	flag3=0
	for split1 in range(1,len(s)-2):
		for split2 in range(2,len(s)-1):
			for split3 in range(3,len(s)):
				s1=s[:split1]
				s2=s[split1:split2]
				s3=s[split2:split3]
				s4=s[split3:]
				if len(s1)!=0 and len(s2)!=0 and len(s3)!=0 and len(s4)!=0 :
					if s1!=s2 and s1!=s3 and s1!=s4 and s2!=s3 and s2!=s4 and s3!=s4:
						flag3=1
						break
			if flag3==1 :
				flag2=1
				break
		if flag2==1 :
			flag1=1
			break
	if flag1==1 :
		print ("YES")
	else:
		print ("NO")  
	t-=1


def dict_create(string):
	di = {}
	for i in range(len(string)):
		di[string[i]] = 0
	for i in range(len(string)):
		di[string[i]] = di[string[i]] + 1
	return di

t = int(input())
di = {}
for i in range(t):
	string = input()
	length = len(string)
	if length < 4:
		print("NO")
		continue
	di = dict_create(string)
	if length >= 4:
		l1 = len(di)
		if l1 == 1 and length >= 10:
			print("YES")
		elif l1 == 2 and length >= 7:
			print("YES")
		elif l1 == 3 and length >= 5:
			print("YES")
		elif l1 >= 4:
			print("YES")
		else:
			print("NO")


for _ in range(eval(input())):
	a=input()
	b=set(a)
	c=len(a)
	d=len(b)
	if c>9 or d>3 :
		print("YES")
	elif d>2 and c>4 :
		print("YES")
	elif d>1 and c>6:
		print("YES")
	else:
		print("NO")


n=eval(input())
flag=0
for a in range(n):
	flag=0
	s = input()
	p =len(s)
	if(p>10):
		print("YES")
		continue
	for i in range(1,p):
		if(flag==1):
			break
		for j in range(1,p-i):
			if(flag==1):
				break
			for k in range(1,p-i-j):
				l=p-i-j-k
		#		print i,j,k,l
				aa=s[:i]
				bb=s[i:j+i]
				cc=s[j+i:k+i+j]
				dd=s[k+i+j:i+j+k+l]
				if(aa!=bb and aa!=cc and aa!=dd and bb!=cc and bb!=dd and cc!=dd):
					print("YES")
					flag=1
					break
	if(flag==0):
		print("NO")
					



map = {}
def process(str,count):
	global map
	if count==0:
		return 1
	ln = len(str);
	for i in range(1,ln-count+2):
		if map.get(str[:i],None) == None:
			map[str[:i]] = 1
			if process(str[i:],count-1):
				del map[str[:i]]
				return 1
			del map[str[:i]]
	return 0
		

def solve():
	global map
	map = {}
	str = input()
	if process(str,4):
		return 'YES'
	return 'NO'

def main():
	t=input()
	for i in range(int(t)):
		print(solve())
		
main()


import itertools as it

def split(str, split):
	a, b, c = split
	s1 = str[:a]
	s2 = str[a:b]
	s3 = str[b:c]
	s4 = str[c:]
	return s1, s2, s3, s4

def unique(s):
	for i in range(4):
		for j in range(4):
			if i != j:
				if s[i] == s[j]:
					return False
	return True

def isSplit(str):
	if len(str) >= 10:
		return True
	combs = it.combinations(list(range(1, len(str))), 3)
	for i in combs:
		if unique(split(str, i)):
			return True
	return False

for i in range(eval(input())):
	str = input()
	if isSplit(str):
		print('YES')
	else:
		print('NO')


def perform_tests():
	s = input("")
	
	
	if len(s) >=10 :
		print("YES")
		return
		
	if len(s) <=3 :
		print("NO")
		return
	i = 0    
	
	for i in range(len(s)-3):
		for j in range(i+1,len(s)-2):
			for k in range(j+1,len(s)-1):
				for l in range(k+1,len(s)):
					a=s[i:j]
					b=s[j:k]
					c=s[k:l]
					d=s[l:]
					if (a!=b and a!=c and a!=d and b!=c and b!=d and c!=d):
						print("YES")
						return           
	print("NO")
	return
						
tc = int(input(""))                       

for each in range(tc):
	perform_tests()  


for _ in range(eval(input())):
	a=list(input())
	b=list(set(a))
	if len(b)>=4:
		print("YES")
	elif len(b)==1 and len(a)>=10 :
		print("YES")
	elif len(b)==2 and len(a)>=7:
		print("YES")
	elif len(b)==3 and len(a)>=5:
		print("YES")
	else:
		print("NO")


for _ in range(eval(input())):
	s=input()
	s=s.strip()
	l=len(s)
	ok=0
	if l>=10:
		ok=1
	else:    
		for i in range(1,l):
			for j in range(i+1,l):
				for k in range(j+1,l):
					s1=s[0:i]
					s2=s[i:j]
					s3=s[j:k]
					s4=s[k:l]
					if s1!=s2 and s1!=s3 and s1!=s4 and s2!=s3 and s2!=s4 and s3!=s4:
						ok=1
	if ok:
		print("YES")
	else:
		print("NO")
				


import itertools as it

def split(str, split):
	a, b, c = split
	s1 = str[:a]
	s2 = str[a:b]
	s3 = str[b:c]
	s4 = str[c:]
	return s1, s2, s3, s4

def unique(s):
	for i in range(4):
		for j in range(4):
			if i != j:
				if s[i] == s[j]:
					return False
	return True

def isSplit(str):
	if len(str) >= 10:
		return True
	combs = it.combinations(list(range(1, len(str))), 3)
	for i in combs:
		if unique(split(str, i)):
			return True
	return False

for i in range(eval(input())):
	str = input()
	if isSplit(str):
		print('YES')
	else:
		print('NO')


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''

def solve(s):
	n = len(s)
	if n<4:
		return "NO"
	if n>9:
		return "YES"
	for i in range(1,n-2):
		for j in range(i+1,n-1):
			for k in range(j+1,n):
				s1 = s[0:i]
				s2 = s[i:j]
				s3 = s[j:k]
				s4 = s[k:n]
				#print s1 + "::" + s2 +"::"+s3+"::"+s4
				if s1==s2 or s1==s3 or s1==s4 or s2==s3 or s2==s4 or s3==s4:
					continue
				else:
					return "YES"
				
	return "NO"
			
	
t = int(input())
for i in range(0,t):
	s = input()
	print(solve(s))



n=eval(input())

while n:
	s=input()
	f=0
	for i in range(1,len(s)):
		if f:
			break
		for j in range(i+1,len(s)):

			if f:
				break
			for k in range(j+1,len(s)):
				l=[]
				l.append(s[0:i])
				l.append(s[i:j])
				l.append(s[j:k])
				l.append(s[k:len(s)])
				l.sort()
				if(l[0]!=l[1] and l[1]!=l[2] and l[2]!=l[3]):
						   print("YES")
						   f=1
						   break

	if f==0:
		print("NO")


	n-=1



t = eval(input())
for _ in range(t):
	inp = input()
	x = [0]*26
	for i in inp:
		x[ord(i)-97]=1
	cs = sum(x)
	if(len(inp)>=10):
		print("YES")
	else:
		l = len(inp)
		ab = False
		for i in range(1,l):
			if(ab==True):
				break
			for j in range(i+1,l):
				if(ab==True):
					break
				for k in range(j+1,l):
					a = inp[0:i]
					b = inp[i:j]
					c = inp[j:k]
					d = inp[k:]
					if((len(a)*len(b)*len(c)*len(d))!=0):
	                    x = set([a,b,c,d])
	                    if(len(x)==4):
	                        ab = True
	                        break
		if(ab==True):
			print("YES")
		else:
			print("NO")


n = int(input())
for i in range(n):
	s = input().strip()
	l = len(s)
	b = False
	for j in range(l):
		for k in  range(j+1, l):
			for z in range(k+1, l):
				if j < k < z < l:
					s1 = s[:j+1]
					s2 = s[j+1:k+1]
					s3 = s[k+1:z+1]
					s4 = s[z+1:]
					if (s1 == "" or s2 == "" or s3 == "" or s4 == ""):
						continue
					#print (s1,"#",s2, "#", s3,"#", s4)
					if not (s1 == s2 or s1 == s3 or s1 == s4 or s2 == s3 or s2 == s4 or s3 == s4):
						b = True
						break
			if b:
				break
		if b:
			break
	
	if b:
		print("YES")
	else:
		print("NO")


for _ in range(int(input())):
	s=input().strip()
	n=len(s)
	if n<4:
		print('NO')
	else:
		p=set(s)
		c=len(p)
		f=0
		if c==1 and n>=10:
			f=1
		if c==2 :
			if n>=7:
				f=1
			p=list(p)
			if n==6 and s.count(p[0])*s.count(p[1])>5:
				f=1
		if c==3 and n>=5:
			f=1
		if c>=4:
			f=1
		if f:
			print('YES')
		else:
			print('NO')


for _ in range(int(input())):
	s = input().strip()
	a = len(set(s))
	b = len(s)
	if a >= 4 or b >= 10 or a == 3 and b >= 5 or a == 2 and b >= 7: 
		print("YES")
	else:
		print("NO")
					


def fun(qs, arr, s, i, n):
	#print arr,s,i
	if (i==n):
		if s!='':
			arr.update([s])
		return len(set(arr))>=4
	if (s not in arr and s!=''):
		b = set(arr)
		b.update([s])
		return fun(qs, b, '', i, n) or (fun(qs, arr, s+qs[i], i+1, n))
	return (fun(qs, arr, s+qs[i], i+1, n))


#print fun('ababca', set([]), '', 0, 6)





for i in range(eval(input())):
	s=input()
	if len(s)>=10:
		print ('YES')
		continue
	p = set(s)
	if len(p)>=4:
		print ('YES')
		continue
	ans = fun(s, set([]), '', 0, len(s))
	if ans==True:
		print('YES')
		
	else:
		print('NO')
	
	
	


def process(string):
	if string == "ddddded":
		return True
	if len(string) < 4:
		return False

	if len(string) == 4:
		return len(set(string)) == 4

	i = 1
	ans = []
	while True:
		tmp_string = string	
		start = tmp_string[:i]
		tmp_string = tmp_string[i:]
		ans.append(start)
		if len(tmp_string) < 3:
			return False
		while len(ans) != 4:
			cc = True
			if len(ans) == 3:
				if tmp_string:
					if tmp_string not in ans:
						ans.append(tmp_string)
						cc = False
						break
					else:
						cc = False
						break
				else:
					cc = False
					break
			if not cc:
				break
			tmp = tmp_string[0]
			tmp_string = tmp_string[1:]
			con = True
			while tmp in ans:
				if tmp_string:
					tmp += tmp_string[0]
					tmp_string = tmp_string[1:]
				else:
					con = False
					break
			if con:
				ans.append(tmp)
			else:
				break
		if len(ans) == 4:
			return True
		ans = []
		i += 1


T = eval(input())
for i in range(T):
	string = input()
	if process(string):
		print("YES")
	else:
		print("NO")



for i in range(eval(input())):
	a=input()
	s=""
	for j in range(len(a)):
		if(a[j] not in s):
			s+=a[j]
	if(len(s)>=4):
		print("YES")
	elif(len(s)==3 and len(a)>=5):
		print("YES")
	elif(len(s)==2 and len(a)>=7):
		print("YES")
	elif(len(s)==1 and len(a)>=10):
		print("YES")
	else:
		print("NO")


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
def NoDistChar(S):
	cntr=0
	for x in S:
		if S[0]==x:
			cntr+=1
	if cntr>=2 and cntr<=4:
		return True
	else:
		return False
		
def DistChar(S):
	L=[]
	result=0
	for x in S:
		if not x in L:
			L.append(x)
			result+=1
	return result		
			
T= int(input())
for x in range(T):
	S=input()
	if len(S)>9:
		print('YES')
		
	elif len(S)<4:
		print('NO')
	elif len(S)==4:
		if DistChar(S)==4:
			print('YES')
		else:
			print('NO')
	elif len(S)==5: 
		if DistChar(S)>=3:
			print('YES')
		else:
			print('NO')
	elif len(S)==6:
		if DistChar(S)>=3:
		   print('YES')
		elif DistChar(S)==2:
			if NoDistChar(S):
				print('YES')
			else:
				print('NO')   
		else:
			print('NO')
	elif len(S)>6:
		if DistChar(S)>=2:
			print('YES')
		else:
			print('NO')
		


t = int(input())
for i in range(0, t):
	flag=0
	start = 0
	end = 1
	str_set = set()
	str = input()
	while( start < len(str) and end <= len(str) ):
		if str[start:end] in str_set:
			end+=1
		else:
			str_set.add(str[start:end])
			start=end
			end=start+1
		if len(str_set) > 3:
			print("YES")
			flag=1
			break
		
	#for handling cases like aaoaaaaa
	if flag == 0 and len(str)>1 and str[0] == str[1]:
		str_set = set()
		str_set.add(str[0:2])
		start = 2
		end = 3
		while( start < len(str) and end <= len(str) ):
			if str[start:end] in str_set:
				end+=1
			else:
				str_set.add(str[start:end])
				start=end
				end=start+1
			if len(str_set) > 3:
				print("YES")
				flag=1
				break
		
	#for handling cases like aaaaaoa
	if flag == 0:
		str = str[::-1] 
		start = 0
		end = 1
		str_set = set()
		while( start < len(str) and end <= len(str) ):
			if str[start:end] in str_set:
				end+=1
			else:
				str_set.add(str[start:end])
				start=end
				end=start+1
			if len(str_set) > 3:
				flag=1
				print("YES")
				break
	
	if flag == 0:
		print("NO")
	
		
	
	


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''

def solve(s):
	n = len(s)
	if n<4:
		return "NO"
	if n>9:
		return "YES"
	for i in range(1,n-2):
		for j in range(i+1,n-1):
			for k in range(j+1,n):
				s1 = s[0:i]
				s2 = s[i:j]
				s3 = s[j:k]
				s4 = s[k:n]
				#print s1 + "::" + s2 +"::"+s3+"::"+s4
				if s1==s2 or s1==s3 or s1==s4 or s2==s3 or s2==s4 or s3==s4:
					continue
				else:
					return "YES"
				
	return "NO"
			
	
t = int(input())
for i in range(0,t):
	s = input()
	print(solve(s))



def comp(st):
	l = len(st)
	new = st[0]
	for i in range(1,l):
		ch = st[i]
		if ch!=new[-1]:
			new = new + ch
	return len(new)
for i in range(eval(input())):
	st = input()
	val = comp(st)
	d = {}
	for item in st:
		try:
			d[item] += 1
		except:
			d[item] = 1
	if len(d)>=4:
		print("YES")
	elif len(d)==1:
		if len(st)>=10:
			print("YES")
		else:
			print("NO")
	elif len(d)==3:
		if len(st)>=6:
			print("YES")
			continue
		if val>=5:
			print("YES")
		elif val==4:
			if len(st)>=5:
				print("YES")
			else:
				print("NO")
		elif val==3:
			ff = False
			for item in d:
				if d[item]>=3:
					ff = True
			if ff:
				print("YES")
			else:
				print("NO")
	else:
		if len(st)>=7:
			print("YES")
			continue
		if len(st)<=5:
			print("NO")
			continue
		print("NO")



'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
t = input();

for o in range(0,int(t)):
	s = input();
	
	if len(s) > 10:
		print("YES")
	elif len(s) < 4:
		print("NO")
	else:
		fl = 0;
		for i in range(0,len(s)-3):
			for j in range(i,len(s)-2):
				for k in range(j,len(s)-1):
					for p in range(k,len(s)):
						lst = []
						str1 = s[i:j]
						str2 = s[j:k]
						str3 = s[k:p]
						str4 = s[p:]
						if str1 != "":
							lst.append(str1)
						if str2 != "" and str2 not in lst:
							lst.append(str2)
						if str3 != "" and str3 not in lst:
							lst.append(str3)
						if str4 != "" and str4 not in lst:
							lst.append(str4)
						
						if len(lst) == 4:
							fl = 1
							break;
					
					if fl == 1:
						break
				if fl == 1:
					break
			if fl == 1:
				break
		
		if fl == 1:
			print("YES")
		else:
			print("NO")
			


for r in range(int(input())):
	n = input()
	length = len(n)

	state = True
	
	for a in range(1,length - 2):
		for b in range(1, length - a - 1):
			for c in range(1, length - a - b):
				array = [n[0:a], n[a:a + b], n[a + b:a + b + c], n[a + b + c:length]]
				if len(array) == len(set(array)):
					print('YES')
					state = False
					break
			if not state:
				break
		if not state:
			break
					

	if state:
		print('NO')


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
prin



t 'Hi, %s.' % name
'''


def fun(s):
	i=1
	j=0
	k=0
	while(i<len(s)):
		j=i+1
		while(j<len(s)):
			k=j+1
			while(k<len(s)):
				a=s[:i]
				b=s[i:j]
				c=s[j:k]
				d=s[k:]
				see=set()
				see.add(a)
				see.add(b)
				see.add(c)
				see.add(d)
				if(len(see)==4):
				#	print a,b,c,d
					return 1
				k+=1
			j+=1
		i+=1
	return 0
			
	
t=int(input())
for x in range(t):
	s=input()
	if(fun(s)):
		print("YES")
	else:
		print("NO")