One day, Chef prepared D brand new dishes. He named the i-th dish by a string Si. After the cooking, he decided to categorize each of these D dishes as special or not.

A dish Si is called special if it's name (i.e. the string Si) can be represented in the form of a double string by removing at most one (possibly zero) character from it's name from any position. 

A string is called a double string if it can be represented as a concatenation of two identical, non-empty strings. 
e.g. "abab" is a double string as it can be represented as "ab" + "ab" where + operation denotes concatenation. 
Similarly, "aa", "abcabc" are double strings whereas "a", "abba", "abc" are not.

-----Input-----
- First line of the input contains an integer D denoting the number of dishes prepared by Chef on that day.
- Each of the next D lines will contain description of a dish. 
	
- The i-th line contains the name of i-th dish Si.
	

-----Output-----
For each of the D dishes, print a single line containing "YES" or "NO" (without quotes) denoting whether the dish can be called as a special or not.

-----Constraints-----
- 1 ≤ D ≤ 106
- 1 ≤ |Si| ≤ 106.
- Each character of string Si will be lower case English alphabet (i.e. from 'a' to 'z').

-----Subtasks-----
Subtask #1 : (20 points)
- Sum of |Si| in an input file doesn't exceed 2 * 103

Subtask 2 : (80 points) 
- Sum of |Si| in an input file doesn't exceed 2 * 106

-----Example-----
Input:
3
aba
abac
abcd

Output:
YES
NO
NO


-----Explanation-----
Example case 1.
We can remove the character at position 1 (0-based index) to get "aa" which is a double string. Hence, it is a special dish.

Example case 2.
It is not possible to remove the character at any of the position to get the double string. Hence, it is not a special dish.

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

String algorithms

Amortized analysis

Data structures

Ad-hoc
Skill types: Data structures

Amortized analysis

Starter code:

Solutions:
from collections import Counter

def is_subseq(s1, s2):
	m = len(s1)
	n = len(s2)
	i = 0
	c = 0
	j = 0
	while i < m and j < n:
		if s1[i] == s2[j]:
			i += 1
			j += 1
			c += 1
		else:
			j += 1
	return c == m

def is_good(s):
	n = len(s)
	return s[0:n // 2] == s[n // 2:]
for _ in range(int(input())):
	s = input()
	n = len(s)
	if len(s) == 1:
		print('NO')
		continue
	if n & 1 == 0:
		if s[0:n // 2] == s[n // 2:]:
			print('YES')
		else:
			print('NO')
	else:
		h = n // 2
		if is_subseq(s[0:h], s[h:]) or is_subseq(s[h + 1:], s[0:h + 1]) or is_good(s[0:n // 2] + s[n // 2 + 1:]):
			print('YES')
		else:
			print('NO')


for case in range(int(input())):
	s = input()
	n = len(s) // 2
	if len(s) == 1:
		print('NO')
	elif len(s) % 2 == 0:
		print('YES' if s[0:n] == s[n:] else 'NO')
	else:
		match = True
		skip = 0
		for i in range(n):
			if s[i + skip] != s[i + n + 1]:
				if skip == 1 or s[i + 1] != s[i + n + 1]:
					match = False
					break
				skip = 1
		if match:
			print('YES')
			continue
		match = True
		skip = 0
		for i in range(n):
			if s[n - 1 - i] != s[2 * n - i - skip]:
				if skip == 1 or s[n - 1 - i] != s[2 * n - i - 1]:
					match = False
					break
				skip = 1
		if match:
			print('YES')
		else:
			print('NO')


def r(s, b):
	(n, m) = (len(s), 0)
	if n == 1:
		return False
	(i, j, f) = (0, n // 2 + b, False)
	while m < n // 2:
		if s[i] != s[j]:
			if f:
				return False
			else:
				f = True
				if b:
					i += 1
				else:
					j += 1
		else:
			i += 1
			j += 1
			m += 1
	return True

def sp(s):
	n = len(s)
	if n % 2 == 0:
		return all((s[i] == s[n // 2 + i] for i in range(n // 2)))
	else:
		return r(s, True) or r(s, False)
for d in range(int(input())):
	print('YES' if sp(input()) else 'NO')


f = 0
t = int(input())
while t > 0:
	t -= 1
	o = 0
	s = input()
	s = list(s)
	n = len(s)
	if len(s) == 1:
		print('NO')
		continue
	if len(s) % 2 == 1:
		for i in range(n):
			ls = s.copy()
			ls.pop(i)
			if ls[0:int(len(ls) / 2)] == ls[int(len(ls) / 2):int(len(ls))]:
				print('YES')
				o = 1
				break
		if o == 0:
			print('NO')
	elif s[0:int(len(s) / 2)] == s[int(len(s) / 2):int(len(s))]:
		print('YES')
	else:
		print('NO')


from string import ascii_lowercase

def fun(str, ch):
	fla = False
	for i in range(len(s)):
		if str[i] == ch:
			h = str[:i] + str[i + 1:]
			d = len(h) // 2
			if h[:d] == h[d:]:
				fla = True
				break
	return fla
T = int(input())
for i in range(T):
	s = str(input())
	if len(s) == 1:
		print('NO')
		continue
	k = 0
	p = '0'
	flag = True
	for j in ascii_lowercase:
		z = s.count(j)
		if z % 2 != 0:
			k = k + 1
			if k >= 2:
				flag = False
				break
			p = j
	if flag == False:
		print('NO')
		continue
	if p != '0':
		if fun(s, p):
			print('YES')
			continue
	else:
		g = len(s) // 2
		if s[:g] == s[g:]:
			print('YES')
			continue
	print('NO')


t = int(input())
for _ in range(t):
	s = input()
	if len(s) % 2 == 0:
		ok = True
		for i in range(len(s) // 2):
			if s[i] != s[i + len(s) // 2]:
				ok = False
				break
		if ok:
			print('YES')
		else:
			print('NO')
	elif len(s) == 1:
		print('NO')
	else:
		idx1 = 0
		idx2 = len(s) // 2
		ok = False
		while idx1 < len(s) // 2 and idx2 < len(s):
			if s[idx1] != s[idx2]:
				idx2 += 1
			else:
				idx1 += 1
				idx2 += 1
		if idx1 == len(s) // 2:
			ok = ok or True
		idx1 = len(s) // 2 + 1
		idx2 = 0
		while idx1 < len(s) and idx2 <= len(s) // 2:
			if s[idx1] != s[idx2]:
				idx2 += 1
			else:
				idx1 += 1
				idx2 += 1
		if idx1 == len(s):
			ok = ok or True
		if ok:
			print('YES')
		else:
			print('NO')


def is_subsequence(A, B):
	i = 0
	j = 0
	while i < len(A) and j < len(B):
		if B[j] == A[i]:
			i += 1
		j += 1
	return i == len(A)

def is_dish_special(S):
	len_over_2 = len(S) // 2
	if len(S) % 2 == 0:
		return is_subsequence(S[0:len_over_2], S[len_over_2:])
	else:
		return is_subsequence(S[0:len_over_2], S[len_over_2:]) or is_subsequence(S[len_over_2 + 1:], S[0:len_over_2 + 1])
D = int(input())
for d in range(D):
	S = input().strip()
	if len(S) == 1:
		print('NO')
	elif is_dish_special(S):
		print('YES')
	else:
		print('NO')


import math
import numpy as np
import pandas as pd
import itertools
import collections
from collections import Counter
import copy as deepcopy

def is_double(s):
	n = len(s)
	if n % 2 == 1:
		return False
	elif n == 0:
		return False
	elif s[:n // 2] != s[n // 2:n]:
		return False
	else:
		return True
try:
	T = int(input())
	for l in range(T):
		s = input()
		n = len(s)
		if is_double(s):
			print('YES')
		else:
			flag = False
			for i in range(n):
				if is_double(s[:i] + s[i + 1:]):
					flag = True
					break
			if flag:
				print('YES')
			else:
				print('NO')
except EOFError:
	pass


t = int(input())
while t > 0:
	s = input()
	n = len(s)
	f = 0
	if n == 1:
		f = 0
	elif len(s) % 2 == 0:
		if s[0:n // 2] == s[n // 2:]:
			f = 1
	else:
		l = (n + 1) // 2
		for i in range(l):
			if i == l - 1:
				a = s[0:i] + s[i + 1:len(s)]
				h = len(a) // 2
				if a[0:h] == a[h:len(a)]:
					f = 1
					break
				else:
					f = 0
					break
			if s[i] == s[l + i]:
				pass
			else:
				a = s[0:i] + s[i + 1:len(s)]
				if a[0:len(a) // 2] == a[len(a) // 2:len(a)]:
					f = 1
					break
				else:
					a = s[0:l + i] + s[l + 1 + i:len(s)]
					if a[0:len(a) // 2] == a[len(a) // 2:len(a)]:
						f = 1
						break
	if f == 0:
		print('NO')
	else:
		print('YES')
	t -= 1


def specialname(z):
	yes = 'YES'
	no = 'NO'
	lz = len(z)
	if lz == 1:
		return no
	hl = lz // 2
	if lz % 2 == 0:
		if z[:hl] == z[hl:]:
			return yes
		else:
			return no
	else:
		hist = dict()
		for c in z:
			if c in hist:
				hist[c] += 1
			else:
				hist[c] = 1
		if len(hist) == 1:
			return yes
		oddc = ''
		for (c, f) in hist.items():
			if f % 2 == 1:
				if oddc != '':
					return no
				else:
					oddc = c
		w = z.replace(oddc, '')
		if w[:len(w) // 2] != w[len(w) // 2:]:
			return no
		pos = -1
		rc = hist[oddc]
		while rc > 0:
			pos = z.find(oddc, pos + 1)
			w = z[:pos] + z[pos + 1:]
			if w[:hl] == w[hl:]:
				return yes
			while z[pos] == oddc:
				rc -= 1
				if rc == 0:
					return no
				pos += 1
for _ in range(int(input())):
	print(specialname(input().strip()))


t = int(input())
for i in range(t):
	s = input()
	x = len(s)
	if x == 1:
		print('NO')
	elif x % 2 == 0:
		if s[:x // 2] == s[x // 2:]:
			print('YES')
		else:
			print('NO')
	else:
		top = 0
		tor = 0
		list = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
		for j in range(x):
			list[ord(s[j]) - 97] += 1
		for j in range(26):
			if list[j] % 2 != 0:
				tor = j + 97
				break
		for j in range(x):
			if tor == ord(s[j]):
				if j == 0:
					s1 = s[j + 1:]
				elif j == x - 1:
					s1 = s[:j]
				else:
					s1 = s[:j] + s[j + 1:]
				if s1[:(x - 1) // 2] == s1[(x - 1) // 2:]:
					print('YES')
					top = 1
					break
		if top != 1:
			print('NO')


def isdoub(s):
	if len(s) == 1:
		return 'NO'
	if len(s) % 2 == 0:
		if s[0:len(s) // 2] == s[len(s) // 2:]:
			return 'YES'
		return 'NO'
	for _ in range(2):
		u = s[0:len(s) // 2]
		v = s[len(s) // 2:]
		for i in range(len(v)):
			if i >= len(u) or u[i] != v[i]:
				v = v[:i] + v[i + 1:]
				break
		if u == v:
			return 'YES'
		s = ''.join(reversed(s))
	return 'NO'
for _ in range(int(input())):
	print(isdoub(input()))


test = int(input())
for i in range(test):
	chs = input()
	lt = len(chs)
	if lt == 1:
		print('NO')
	elif lt % 2 == 0:
		if chs[:lt // 2] == chs[lt // 2:]:
			print('YES')
		else:
			print('NO')
	else:
		d1 = 0
		d2 = 0
		diction = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
		for k in range(lt):
			diction[ord(chs[k]) - 97] += 1
		for k in range(26):
			if diction[k] % 2 != 0:
				d2 = k + 97
				break
		for k in range(lt):
			if d2 == ord(chs[k]):
				if k == 0:
					aux = chs[k + 1:]
				elif k == lt - 1:
					aux = chs[:k]
				else:
					aux = chs[:k] + chs[k + 1:]
				if aux[:(lt - 1) // 2] == aux[(lt - 1) // 2:]:
					print('YES')
					d1 = 1
					break
		if d1 != 1:
			print('NO')


t = int(input())
for i in range(t):
	s = input()
	if len(s) == 0 or len(s) == 1:
		print('NO')
	else:
		if len(s) % 2 == 0:
			flag = False
			half = int(len(s) / 2)
			if s[0:half] == s[half:len(s)]:
				flag = True
			else:
				flag = False
		else:
			flag = False
			l = int((len(s) + 1) / 2)
			news = s
			for j in range(l):
				if j == l - 1:
					news = s[0:j] + s[j + 1:len(s)]
					half = int(len(news) / 2)
					if news[0:half] == news[half:len(news)]:
						flag = True
						break
					else:
						flag = False
						break
				if s[j] == s[l + j]:
					pass
				else:
					news = s[0:j] + s[j + 1:len(s)]
					if news[0:int(len(news) / 2)] == news[int(len(news) / 2):len(news)]:
						flag = True
						break
					else:
						news = s[0:l + j] + s[l + 1 + j:len(s)]
						if news[0:int(len(news) / 2)] == news[int(len(news) / 2):len(news)]:
							flag = True
							break
		if flag:
			print('YES')
		else:
			print('NO')


t = int(input())
while t:
	s = input()
	l = len(s)
	if l == 1:
		print('NO')
		t -= 1
		continue
	if l % 2 == 0:
		if s[:len(s) // 2] == s[len(s) // 2:]:
			print('YES')
		else:
			print('NO')
	else:
		i = 0
		j = l // 2 + 1
		count = 0
		while i <= l // 2 and j < l:
			if s[i] == s[j]:
				i += 1
				j += 1
				continue
			else:
				i += 1
				count += 1
		if i > l // 2 and j >= l and (count < 2):
			print('YES')
			t -= 1
			continue
		i = 0
		j = l // 2 + 1
		flag = True
		while i < l // 2 and j < l:
			if s[i] == s[j]:
				i += 1
				j += 1
				continue
			else:
				flag = False
				break
		if i == l // 2 and j == l and (flag == True):
			print('YES')
			t -= 1
			continue
		i = 0
		j = l // 2
		count = 0
		while i < l // 2 and j < l:
			if s[i] == s[j]:
				i += 1
				j += 1
				continue
			else:
				j += 1
				count += 1
		if i >= l // 2 and j >= l - 1 and (count < 2):
			print('YES')
			t -= 1
			continue
		print('NO')
	t -= 1


d = int(input())
ans = []
n = d
while d > 0:
	flag = 0
	s = input()
	l = len(s)
	l1 = int(l / 2)
	a = []
	for i in range(26):
		a.append([])
	if l % 2 == 1:
		count = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
		for i in range(l):
			count[ord(s[i]) - 97] = count[ord(s[i]) - 97] + 1
			a[ord(s[i]) - 97].append(i)
		for i in range(26):
			if count[i] % 2 == 1:
				l2 = len(a[i])
				for j in range(l2):
					pos = a[i][j]
					if l1 <= pos:
						str1 = s[0:l1]
					else:
						str1 = s[0:pos] + s[pos + 1:l1 + 1]
					if l1 > pos:
						str2 = s[l1 + 1:]
					else:
						str2 = s[l1:pos] + s[pos + 1:]
					if str1 == str2 and str1 != '' and (str2 != ''):
						flag = 1
						break
	else:
		str1 = s[0:l1]
		str2 = s[l1:]
		if str1 == str2:
			flag = 1
	if flag == 1:
		ans.append('YES')
	else:
		ans.append('NO')
	d = d - 1
for i in range(n):
	print(ans[i])


for t in range(int(input())):
	s = list(input())
	l = len(s)
	if l == 1:
		print('NO')
		continue
	if l % 2 == 0:
		print('YES' if s[:l // 2] == s[l // 2:] else 'NO')
	else:
		s1 = s[:l // 2]
		s2 = s[l // 2:l]
		for (v, (a, b)) in enumerate(zip(s1, s2)):
			if not a == b:
				s2.pop(v)
				break
		else:
			s2.pop()
		if s1 == s2:
			print('YES')
		else:
			s1 = s[:l // 2 + 1]
			s2 = s[l // 2 + 1:]
			for (v, (a, b)) in enumerate(zip(s1, s2)):
				if not a == b:
					s1.pop(v)
					break
			else:
				s1.pop()
			print('YES' if s1 == s2 else 'NO')


for _ in range(int(input())):
	s = input()
	n = len(s)
	if n == 1:
		print('NO')
		continue
	if n % 2 == 0:
		if s[:n // 2] == s[n // 2:]:
			print('YES')
		else:
			print('NO')
		continue
	(A, B) = (s[:n // 2], s[n // 2:])
	if B[1:] == A:
		print('YES')
		continue
	elif B[:-1] == A:
		print('YES')
		continue
	elif B[-1] != B[0]:
		(i, j) = (0, 0)
		while i != n // 2:
			if A[i] == B[j]:
				i += 1
				j += 1
			elif A[i:] != B[j + 1:]:
				print('NO')
				break
			else:
				print('YES')
				break
	else:
		(i, j, t1) = (0, 0, False)
		while i != n // 2:
			if A[i] == B[j]:
				i += 1
				j += 1
			elif A[i:] == B[j + 1:]:
				t1 = True
				break
			else:
				break
		(i, j, t2) = (0, 1, False)
		while i != n // 2:
			if A[i] == B[j]:
				i += 1
				j += 1
			elif A[i + 1:] == B[j:-1]:
				t2 = True
				break
			else:
				break
		if t1 or t2:
			print('YES')
		else:
			print('NO')


from collections import Counter

def is_spcl(s, n):
	return s[:n // 2] == s[n // 2:]
for _ in range(int(input())):
	s = input()
	n = len(s)
	if len(s) == 1:
		print('NO')
		continue
	if s[0:n // 2] == s[n // 2:]:
		print('YES')
		continue
	f = 0
	for i in range(0, n):
		if is_spcl(s[0:i] + s[i + 1:], n - 1):
			f = 1
			break
	print('YES' if f else 'NO')


import collections
for _ in range(int(input())):
	s = input().strip()
	l = len(s)
	(c, cc) = (0, 0)
	lbt = len(s) // 2
	s1 = s[:lbt]
	s2 = s[lbt:]
	ans = 'YES'
	if l == 1:
		ans = 'NO'
	elif l % 2 == 0:
		if s[:lbt] == s[lbt:]:
			ans = 'YES'
		else:
			ans = 'NO'
	else:
		letters = dict(collections.Counter(s))
		for (k, v) in letters.items():
			if v % 2 != 0:
				cc += 1
				if cc > 1:
					ans = 'NO'
					break
		if ans != 'NO':
			(i, j) = (0, lbt + 1)
			c = 0
			while i < lbt + 1 and j < l:
				if s[i] == s[j]:
					c += 1
					i += 1
					j += 1
				else:
					i += 1
					if i < lbt + 1 and j < l and (s[i] == s[j]):
						c += 1
						i += 1
						j += 1
					else:
						break
			if c != lbt:
				(c, i, j) = (0, 0, lbt)
				while i < lbt and j < l:
					if s[i] == s[j]:
						c += 1
						i += 1
						j += 1
					else:
						j += 1
						if i < lbt and j < l and (s[i] == s[j]):
							c += 1
							i += 1
							j += 1
						else:
							break
			if c == lbt:
				ans = 'YES'
			else:
				ans = 'NO'
	print(ans)


def offbyone(plus, ref):
	lp = len(plus)
	if lp == 2:
		return ref == plus[0] or ref == plus[1]
	sm = lp // 2
	if plus[:sm] == ref[:sm]:
		return offbyone(plus[sm:], ref[sm:])
	elif plus[sm + 1:] == ref[sm:]:
		return offbyone(plus[:sm + 1], ref[:sm])
	else:
		return False

def specialname(z):
	yes = 'YES'
	no = 'NO'
	lz = len(z)
	if lz == 1:
		return no
	hl = lz // 2
	if lz % 2 == 0:
		if z[:hl] == z[hl:]:
			return yes
		else:
			return no
	elif offbyone(z[:hl + 1], z[hl + 1:]) or offbyone(z[hl:], z[:hl]):
		return yes
	else:
		return no
for _ in range(int(input())):
	print(specialname(input().strip()))


t = int(input())
for ti in range(t):
	s = input().strip()
	l = len(s)
	if l == 1:
		print('NO')
	elif l % 2 == 0:
		if s[:l // 2] == s[l // 2:]:
			print('YES')
		else:
			print('NO')
	else:
		special = False
		x = 0
		for c in s:
			x = x ^ ord(c)
		c = chr(x)
		if c in s:
			k = (l - 1) // 2
			n = s.count(c)
			i = 0
			while (n > 0) & (not special):
				i = s.find(c, i)
				news = s[:i] + s[i + 1:]
				if news[:k] == news[k:]:
					special = True
					break
				n = n - 1
				i = i + 1
		if special:
			print('YES')
		else:
			print('NO')


for _ in range(int(input())):
	s = input()
	s = list(s)
	s1 = s
	f = 0
	l = len(s)
	if l >= 2:
		for i in range(l):
			if l % 2 == 0:
				ln = l
				tp1 = s1[:ln // 2]
				tp2 = s1[ln // 2:]
				if str(tp1) == str(tp2):
					f = 1
					break
			elif i == 0:
				tmp = s1[i + 1:]
				ln = l - 1
				tp1 = tmp[:ln // 2]
				tp2 = tmp[ln // 2:]
				if str(tp1) == str(tp2):
					f = 1
					break
			else:
				tmp = s1[:i]
				tmp2 = s1[i + 1:]
				temp = tmp + tmp2
				ln = l - 1
				tp1 = temp[:ln // 2]
				tp2 = temp[ln // 2:]
				if str(tp1) == str(tp2):
					f = 1
					break
		if f == 1:
			print('YES')
		else:
			print('NO')
	elif l == 1:
		print('NO')


t = int(input())
for _ in range(t):
	s = input()
	l = len(s)
	lh = int(l / 2)
	if l % 2 == 0:
		if s[:lh] == s[lh:]:
			print('YES')
		else:
			print('NO')
	elif l == 1:
		print('NO')
	else:
		left = s[:lh]
		right = s[lh:]
		k = 0
		i = 0
		j = 0
		flag1 = True
		while i < len(left):
			if j < len(right) and left[i] == right[j]:
				i += 1
				j += 1
			elif j < len(right) - 1 and left[i] == right[j + 1] and (k < 2):
				i += 1
				j += 2
				k += 1
			else:
				flag1 = False
				break
		left = s[:lh + 1]
		right = s[lh + 1:]
		k = 0
		i = 0
		j = 0
		flag2 = True
		while j < len(right):
			if i < len(left) and left[i] == right[j] and (k < 2):
				i += 1
				j += 1
			elif i < len(left) - 1 and left[i + 1] == right[j] and (k < 2):
				i += 2
				j += 1
				k += 1
			else:
				flag2 = False
				break
		if flag1 or flag2:
			print('YES')
		else:
			print('NO')


def check_equal(a, b):
	index = 0
	for i in a:
		while index < len(b) and i != b[index]:
			index += 1
		if index >= len(b):
			return False
		index += 1
	return True

def Dob_String(n):
	size = len(n)
	midpoint = size // 2
	if check_equal(n[0:midpoint], n[midpoint:size]):
		return 'YES'
	elif size % 2 != 0 and check_equal(n[midpoint + 1:size], n[0:midpoint + 1]):
		return 'YES'
	else:
		return 'NO'
T = int(input())
for _ in range(T):
	n = input()
	if len(n) > 1:
		print(Dob_String(n))
	else:
		print('NO')


def is_subsequence(a, lstart, lend, rstart, rend):
	mismatch = 0
	i = lstart
	j = rstart
	while i <= lend:
		if a[i] != a[j]:
			mismatch += 1
			j += 1
		else:
			i += 1
			j += 1
		if mismatch > 1:
			return False
	return True
for t in range(int(input())):
	a = input()
	n = len(a)
	if len(a) == 1:
		print('NO')
	elif len(a) % 2 == 0:
		if a[0:n // 2] == a[n // 2:n]:
			print('YES')
		else:
			print('NO')
	elif len(a) % 2 != 0:
		if is_subsequence(a, 0, n // 2 - 1, n // 2, n - 1) + is_subsequence(a, n // 2 + 1, n - 1, 0, n // 2):
			print('YES')
		else:
			print('NO')


D = int(input())
for i in range(D):
	now = input()
	len_now = len(now)
	if len_now == 1:
		print('NO')
		continue
	elif len_now % 2 == 0:
		first = 0
		mid = len_now // 2
		second = mid
		while first < mid and now[first] == now[second]:
			first = first + 1
			second = second + 1
		if first == mid:
			print('YES')
			continue
		else:
			print('NO')
			continue
	else:
		flag = 0
		error = 0
		first = 0
		mid = len_now // 2
		second = mid + 1
		while first < mid and now[first] == now[second]:
			first = first + 1
			second = second + 1
		if first == mid:
			print('YES')
			continue
		first = 0
		second = mid + 1
		error = 0
		while first <= mid:
			if now[first] == now[second]:
				first = first + 1
				second = second + 1
			else:
				error = error + 1
				if error > 1:
					break
				else:
					first = first + 1
		if first == mid + 1 and error == 1:
			print('YES')
			continue
		first = 0
		second = mid
		error = 0
		while second < len_now:
			if now[first] == now[second]:
				first = first + 1
				second = second + 1
			else:
				error = error + 1
				if error > 1:
					break
				else:
					second = second + 1
		if second == len_now and error == 1:
			print('YES')
			continue
		print('NO')


t = int(input())
while t:
	t -= 1
	s = input()
	l = len(s)
	if l == 1:
		print('NO')
		continue
	flag = 0
	if l % 2 == 0:
		for i in range(l // 2):
			if s[i] != s[i + l // 2]:
				flag = 1
				break
	else:
		for i in range(l // 2):
			if s[i] != s[i + l // 2 + 1]:
				flag = 1
				break
		if flag:
			flag = 0
			vis = 0
			i = 0
			j = l // 2 + 1
			while i <= l // 2:
				if s[i] != s[j]:
					if vis == 1:
						flag = 1
						break
					else:
						i += 1
						vis = 1
				else:
					i += 1
					j += 1
		if flag:
			flag = 0
			vis = 0
			i = 0
			j = l // 2
			while i < l // 2:
				if s[i] != s[j]:
					if vis == 1:
						flag = 1
						break
					else:
						j += 1
						vis = 1
				else:
					i += 1
					j += 1
	if flag == 0:
		print('YES')
	else:
		print('NO')


q = int(input())
for _ in range(0, q):
	s = input()
	if len(s) == 1:
		print('NO')
	elif len(s) % 2 == 0:
		t = len(s) // 2
		n = len(s)
		if s[0:t] == s[t:n]:
			print('YES')
		else:
			print('NO')
	else:
		n = int(len(s) // 2)
		l = len(s)
		flag = False
		s1 = s[0:n]
		s2 = s[n:l]
		s3 = s[0:n + 1]
		s4 = s[n + 1:l]
		j = 0
		count = 0
		i = 0
		while i < n:
			if not s1[i] == s2[j]:
				j = j + 1
				count += 1
				if count > 1:
					break
			else:
				j += 1
				i += 1
				if count > 1:
					break
		if count >= 2:
			j = 0
			count = 0
			i = 0
			while j < n:
				if not s3[i] == s4[j]:
					i = i + 1
					count += 1
					if count > 1:
						break
				else:
					i = i + 1
					j = j + 1
					if count > 1:
						break
		if count >= 2:
			print('NO')
		else:
			print('YES')


def fnd(s, ch):
	a = []
	for i in range(len(s)):
		if ch == s[i]:
			a += [i]
	return a
t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	if len(s) == 1:
		print('NO')
	elif n % 2 == 0:
		if s[0:n // 2] == s[n // 2:n]:
			print('YES')
		else:
			print('NO')
	else:
		d = [0] * 26
		for i in range(n):
			d[ord(s[i]) - 97] += 1
		f = 1
		p = 0
		k = [0] * 2
		x = 0
		for i in range(26):
			if d[i] % 2 != 0:
				p += 1
				k[x] = i
				x += 1
			if p > 1:
				f = 0
				break
		if f == 0:
			print('NO')
		elif s[0:n // 2] == s[n // 2:n]:
			print('YES')
		else:
			ch1 = chr(k[0] + 97)
			pos = fnd(s, ch1)
			m = 0
			for i in range(len(pos)):
				t = s[0:pos[i]] + s[pos[i] + 1:n]
				if t[0:n // 2] == t[n // 2:n]:
					m = 1
					break
			if m:
				print('YES')
			else:
				print('NO')


import math

def isSubSequence(a, b):
	ans = 'YES'
	l1 = len(a)
	l2 = len(b)
	count = 0
	i = 0
	j = 0
	while i < l1 and j < l2:
		if a[i] == b[j]:
			i += 1
			j += 1
		else:
			count += 1
			j += 1
	if count > 1:
		ans = 'NO'
	return ans

def doubleString(st):
	length = len(st)
	ans = 'NO'
	if length > 1:
		s1 = 0
		s2 = math.ceil(length / 2)
		st1 = st[:length - s2]
		st2 = st[s2:]
		if length % 2 == 0:
			if st1 == st2:
				ans = 'YES'
		elif isSubSequence(st1, st[s2 - 1] + st2) == 'YES' or isSubSequence(st2, st1 + st[s2 - 1]) == 'YES':
			ans = 'YES'
	return ans
D = int(input())
for i in range(D):
	st = input()
	print(doubleString(st))


sub1 = ''
sub2 = ''
substr = ''
for x in range(int(input())):
	str = input().strip()
	m = [0 for i in range(123)]
	l = len(str)
	if l is 1:
		print('NO')
		continue
	for y in range(l):
		m[int(ord(str[y]))] += 1
	count = 0
	for y in range(97, 123):
		if m[y] % 2 is not 0:
			count += 1
			if count is 1:
				ch1 = chr(y)
			if count > 1:
				break
	if count > 1:
		print('NO')
		continue
	if count is 0:
		if l % 2 is not 0:
			print('NO')
		else:
			sub1 = str[0:l // 2]
			sub2 = str[l // 2:l]
			if sub1 == sub2:
				print('YES')
			else:
				print('NO')
	elif count is 1:
		flag = 0
		for y in range(l):
			if str[y] is ch1:
				substr = str[0:y] + str[y + 1:l]
				len1 = l - 1
				sub1 = substr[0:len1 // 2]
				sub2 = substr[len1 // 2:len1]
				if sub1 == sub2:
					print('YES')
					flag = 1
					break
		if flag is 0:
			print('NO')


def isCool(s):
	l = len(s)
	if l == 1:
		return False
	if l % 2 == 0:
		return True if isCool2(s) else False
	mid = True
	idx = -1
	for x in range(l // 2):
		if s[x] != s[l // 2 + x]:
			idx = x
			break
	if idx == -1:
		return True
	idx2 = -1
	for x in range(l // 2):
		if s[x] != s[l // 2 + x + 1]:
			idx2 = x
			break
	if idx2 == -1:
		return True
	a = s[:idx] + s[idx + 1:]
	idx += l // 2
	b = s[:idx] + s[idx + 1:]
	idx = idx2
	c = s[:idx] + s[idx + 1:]
	idx += l // 2
	d = s[:idx] + s[idx + 1:]
	if isCool2(a) or isCool2(b) or isCool2(c) or isCool2(d):
		return True

def isCool2(s):
	l = len(s)
	idx = -1
	for x in range(l // 2):
		if s[x] != s[l // 2 + x]:
			idx = x
			break
	if idx == -1:
		return True
	else:
		return False
n = int(input())
for x in range(n):
	s = input()
	print('YES' if isCool(s) else 'NO')


import sys
from collections import Counter, deque
from math import gcd, sqrt, ceil

def li():
	return [int(i) for i in sys.stdin.readline().split()]

def si():
	return sys.stdin.readline().split()

def ii():
	return int(sys.stdin.readline())

def ip():
	return input()

def sub(x, y):
	i = 0
	for c in x:
		while i < len(y) and y[i] != c:
			i += 1
		if i == len(y):
			return 0
		i += 1
	return 1
for tastcas in range(int(input())):
	a = ip()
	n = len(a)
	m = n // 2
	mm = (n + 1) // 2
	if n < 2:
		print('NO')
	elif sub(a[:m], a[m:]) or sub(a[mm:], a[:mm]):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	s = input().strip()
	l = len(s)
	(c, cc) = (0, 0)
	lbt = len(s) // 2
	s1 = s[:lbt]
	s2 = s[lbt:]
	ans = 'YES'
	if l == 1:
		ans = 'NO'
	elif l % 2 == 0:
		if s[:lbt] == s[lbt:]:
			ans = 'YES'
		else:
			ans = 'NO'
	elif ans != 'NO':
		(i, j) = (0, lbt + 1)
		c = 0
		while i < lbt + 1 and j < l:
			if s[i] == s[j]:
				c += 1
				i += 1
				j += 1
			else:
				i += 1
				if i < lbt + 1 and j < l and (s[i] == s[j]):
					c += 1
					i += 1
					j += 1
				else:
					break
		if c != lbt:
			(c, i, j) = (0, 0, lbt)
			while i < lbt and j < l:
				if s[i] == s[j]:
					c += 1
					i += 1
					j += 1
				else:
					j += 1
					if i < lbt and j < l and (s[i] == s[j]):
						c += 1
						i += 1
						j += 1
					else:
						break
		if c == lbt:
			ans = 'YES'
		else:
			ans = 'NO'
	print(ans)


for _ in range(int(input())):
	s = input()
	n = len(s)
	ans = 'NO'
	if len(s) == 1:
		ans = 'NO'
	elif n % 2 == 0:
		if s[:n // 2] == s[n // 2:]:
			ans = 'YES'
	else:
		s1 = s[:n // 2]
		s2 = s[n // 2:]
		index = n // 2
		for i in range(n // 2):
			if s1[i] != s2[i]:
				index = i
				break
		if s1 == s2[:index] + s2[index + 1:]:
			ans = 'YES'
		else:
			s1 = s[:n // 2 + 1]
			s2 = s[n // 2 + 1:]
			index = n // 2
			for i in range(n // 2):
				if s1[i] != s2[i]:
					index = i
					break
			if s2 == s1[:index] + s1[index + 1:]:
				ans = 'YES'
	print(ans)


def isDouble(s):
	if len(s) % 2 == 1:
		return False
	else:
		return s[:len(s) // 2] == s[len(s) // 2:]

def cal(s):
	l = [0] * 26
	i = 0
	while i < len(s):
		k = ord(s[i])
		l[k - 97] += 1
		i += 1
	i = 0
	c = []
	while i < 26:
		if l[i] % 2 == 1:
			c += [i]
		i += 1
	if len(c) == 1:
		return chr(c[0] + 97)
	else:
		return False

def isSpecial(s):
	if len(s) % 2 == 0:
		return s[:len(s) // 2] == s[len(s) // 2:]
	elif len(s) == 1:
		return False
	else:
		c = cal(s)
		if c == False:
			return False
		else:
			i = 0
			while i < len(s):
				if s[i] == c:
					if isDouble(s[:i] + s[i + 1:]):
						return True
				i += 1
			return False
test = int(input())
while test != 0:
	test -= 1
	s = input()
	if isSpecial(s):
		print('YES')
	else:
		print('NO')


def ds(x, z):
	w = len(x)
	q = len(z)
	i = 0
	j = 0
	f = 0
	h = 0
	while i < w and j < q:
		if x[i] == z[j]:
			i += 1
			j += 1
		else:
			f += 1
			i += 1
			if f > 1:
				h = 1
				break
	if h == 0:
		return True
	else:
		return False
d = int(input())
while d != 0:
	s = str(input())
	b = len(s)
	if b == 1:
		print('NO')
	elif b % 2 == 0:
		f = b // 2
		r = s[0:f]
		p = s[f:]
		if r == p:
			print('YES')
		else:
			print('NO')
	else:
		f = b // 2
		r = s[0:f + 1]
		p = s[f + 1:]
		y = s[0:f]
		t = s[f:]
		if ds(r, p):
			print('YES')
		elif ds(t, y):
			print('YES')
		else:
			print('NO')
	d -= 1


def check(s, l):
	a = s[:l >> 1]
	b = s[l >> 1:]
	cc = 0
	(i, j) = (0, 0)
	while cc < 2 and i < l >> 1 and (j < l - (l >> 1)):
		if a[i] != b[j]:
			cc += 1
			j += 1
		else:
			i += 1
			j += 1
	if cc <= 1:
		return True
	a = s[:(l >> 1) + 1]
	b = s[(l >> 1) + 1:]
	cc = 0
	(i, j) = (0, 0)
	while cc < 2 and i < (l >> 1) + 1 and (j < l - (l >> 1) - 1):
		if a[i] != b[j]:
			cc += 1
			i += 1
		else:
			i += 1
			j += 1
	if cc <= 1:
		return True
	return False
t = int(input())
for k in range(t):
	s = input()
	l = len(s)
	if l == 1:
		print('NO')
		continue
	if l & 1:
		if check(s, l):
			print('YES')
		else:
			print('NO')
	elif s[0:l >> 1] == s[l >> 1:]:
		print('YES')
	else:
		print('NO')


import sys
n = int(input())
for i in range(n):
	s = input()
	m = len(s)
	if m == 1:
		sys.stdout.write('NO\n')
	elif m % 2 != 0:
		i = 0
		j = int(m / 2) + 1
		flag = False
		Flag = True
		while j < m:
			if s[i] != s[j]:
				if not flag:
					flag = True
					i += 1
				else:
					Flag = False
					break
			else:
				i += 1
				j += 1
		if not Flag:
			i = 0
			j = int(m / 2)
			flag = False
			Flag = True
			while j < m:
				if s[i] != s[j]:
					if not flag:
						flag = True
						j += 1
					else:
						Flag = False
						break
				else:
					i += 1
					j += 1
			if Flag:
				sys.stdout.write('YES\n')
			else:
				sys.stdout.write('NO\n')
		else:
			sys.stdout.write('YES\n')
	elif s[:int(m / 2)] == s[int(m / 2):]:
		sys.stdout.write('YES\n')
	else:
		sys.stdout.write('NO\n')


def check(x, y):
	i = 0
	j = 0
	if len(x) < len(y):
		(x, y) = (y, x)
	pos = len(x) - 1
	while i < len(x) and j < len(y):
		if x[i] == y[j]:
			i += 1
			j += 1
		else:
			pos = i
			break
	del x[pos]
	if x == y:
		return True
	return False
t = int(input())
while t:
	t -= 1
	a = list(input())
	n = len(a)
	if n % 2 == 0:
		if a[:n // 2] == a[n // 2:]:
			print('YES')
		else:
			print('NO')
	elif n > 1 and (check(a[:n // 2], a[n // 2:]) or check(a[(n + 1) // 2:], a[:(n + 1) // 2])):
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	s = input()
	l = len(s)
	if l == 1:
		print('NO')
	elif l % 2 == 0:
		if s[:l // 2] == s[l // 2:]:
			print('YES')
		else:
			print('NO')
	else:
		flag = 0
		dica = {}
		pele = 0
		for i in range(l):
			if s[i] in dica.keys():
				dica[s[i]].append(i)
			else:
				dica[s[i]] = [i]
		for k in dica.keys():
			if len(dica[k]) % 2 != 0:
				flag += 1
				pele = k
		if flag != 1:
			print('NO')
		else:
			flag = 0
			for i in dica[pele]:
				ns = s[:i] + s[i + 1:]
				if ns[:(l - 1) // 2] == ns[(l - 1) // 2:]:
					print('YES')
					flag = 1
					break
			if flag == 0:
				print('NO')


def is_subseq(x, y):
	i = 0
	for c in x:
		while i < len(y) and y[i] != c:
			i += 1
		if i == len(y):
			return False
		i += 1
	return True
t = int(input())
while t:
	t -= 1
	a = input()
	n = len(a)
	if n > 1 and (is_subseq(a[:n // 2], a[n // 2:]) or is_subseq(a[(n + 1) // 2:], a[:(n + 1) // 2])):
		print('YES')
	else:
		print('NO')


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log2, ceil
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from bisect import insort
from collections import Counter
from collections import deque
from heapq import heappush, heappop, heapify
from itertools import permutations, combinations
from itertools import accumulate as ac
from random import randint as ri, shuffle
mod = int(1000000000.0) + 7
ip = lambda : int(stdin.readline())
inp = lambda : map(int, stdin.readline().split())
ips = lambda : stdin.readline().rstrip()
out = lambda x: stdout.write(str(x) + '\n')

def check(x, y):
	i = 0
	j = 0
	if len(x) < len(y):
		(x, y) = (y, x)
	pos = len(x) - 1
	while i < len(x) and j < len(y):
		if x[i] == y[j]:
			i += 1
			j += 1
		else:
			pos = i
			break
	del x[pos]
	if x == y:
		return True
	return False
t = int(input())
while t:
	t -= 1
	a = list(input())
	n = len(a)
	if n % 2 == 0:
		if a[:n // 2] == a[n // 2:]:
			print('YES')
		else:
			print('NO')
	elif n > 1 and (check(a[:n // 2], a[n // 2:]) or check(a[(n + 1) // 2:], a[:(n + 1) // 2])):
		print('YES')
	else:
		print('NO')


case = int(input())
for i in range(case):
	st = input()
	x = len(st)
	if x == 1:
		print('NO')
	elif x % 2 == 0:
		if st[:x // 2] == st[x // 2:]:
			print('YES')
		else:
			print('NO')
	else:
		top = 0
		to = 0
		l = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
		for j in range(x):
			l[ord(st[j]) - 97] += 1
		for j in range(26):
			if l[j] % 2 != 0:
				to = j + 97
				break
		for j in range(x):
			if to == ord(st[j]):
				if j == 0:
					s0 = st[j + 1:]
				elif j == x - 1:
					s0 = st[:j]
				else:
					s0 = st[:j] + st[j + 1:]
				if s0[:(x - 1) // 2] == s0[(x - 1) // 2:]:
					print('YES')
					top = 1
					break
		if top != 1:
			print('NO')


__author__ = 'masterchief'

def solve():
	d = int(input())
	for dish in range(d):
		dish_special()

def dish_special():
	name = input()
	special_name = False
	len_name = len(name)
	mid = len_name // 2
	if len_name == 1:
		pass
	elif len_name % 2:
		if match(name[:mid], name[mid:], 1) or match(name[mid + 1:], name[:mid + 1], 1):
			special_name = True
	elif match(name[:mid], name[mid:]):
		special_name = True
	print('YES') if special_name else print('NO')

def match(seq_template, seq_search, fault_tolerance=0):
	len_template = len(seq_template)
	len_search = len(seq_search)
	faults = 0
	i = 0
	while i < len_template:
		if seq_template[i] != seq_search[i + faults]:
			faults += 1
		else:
			i += 1
		if faults > fault_tolerance:
			return False
	return True
solve()


import math
no_of_test_cases = int(input())

def is_subsequence(s1, s2):
	start1 = 0
	start2 = 0
	len1 = len(s1)
	len2 = len(s2)
	while start2 < len2 and start1 < len1:
		if s2[start2] == s1[start1]:
			start1 += 1
		start2 += 1
	return start1 == len1

def is_double_string(s):
	strLen = len(s)
	if strLen == 1:
		return 'NO'
	if strLen % 2 == 0:
		mid = math.floor(strLen / 2)
		return 'YES' if s[0:mid] == s[mid:strLen] else 'NO'
	else:
		start = 0
		mid = math.floor(strLen / 2)
		end = len(s)
		if is_subsequence(s[0:mid], s[mid:end]) or is_subsequence(s[mid + 1:end], s[0:mid + 1]):
			return 'YES'
		return 'NO'
for caseNo in range(1, no_of_test_cases + 1):
	s = input()
	print(is_double_string(s))


def check(a, b):
	p = 0
	a = list(a)
	b = list(b)
	for i in a:
		if b[p] == i:
			p += 1
		if p == len(b):
			break
	if p == len(b):
		return True
	return False
for t in range(int(input())):
	s = str(input())
	l = len(s)
	if l == 1:
		print('NO')
	elif l % 2 != 0:
		s1a = s[0:l // 2]
		s1b = s[l // 2:l]
		s2a = s[0:l // 2 + 1]
		s2b = s[l // 2 + 1:l]
		if check(s1b, s1a) or check(s2a, s2b):
			print('YES')
		else:
			print('NO')
	else:
		s1 = s[0:l // 2]
		s2 = s[l // 2:l]
		if s1 == s2:
			print('YES')
		else:
			print('NO')