Chef has a string $S$ consisting of lowercase English characters. Chef defined functions left shift $L(X)$ and right shift $R(X)$ as follows.
$L(X)$ is defined as shifting all characters of string $X$  one step towards left and moving the first character to the end.
$R(X)$ is defined as shifting all characters of string $X$ one step towards the right and moving the last character to the beginning.

For example, L("abcd") = "bcda" and R("abcd") = "dabc"

Chef wants to find out whether there exists a string $V$ of the same length as $S$ such that both $L(V) = S$ and $R(V) = S$ holds.

------ Input: ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a string $S$.

------ Output: ------
For each test case, If there exists a valid string $V$, print "YES", otherwise print "NO" (without the quotes).

------ Constraints  ------
$1 ≤ T ≤ 100$
$1 ≤ |S| ≤ 10^{6}$
$S$ contains all lower case English alphabets.
It's guaranteed that the total length of the strings in one test file doesn't exceed $10^{6}$

----- Sample Input 1 ------ 
4
a
ab
abcd
aaaaa
----- Sample Output 1 ------ 
YES
YES
NO
YES
----- explanation 1 ------ 
- In the first test case, Chef can choose $V = S$
- In the second test case, Chef can choose $V$ = "ba" which satisfies both conditions.
- There doesn't exist any valid choice for string $V$ in the third test case.

Source: codechef | Difficulty: EASY
Tags: String algorithms

Constructive algorithms

Data structures

Ad-hoc


Solutions:
def ls(s):
	return s[1:] + s[0]

def rs(s):
	return s[-1] + s[:-1]
for _ in range(int(input())):
	s = input()
	sl = ls(s)
	sr = rs(s)
	if sl == sr or s == sl or s == sr:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	a = input()
	b = len(a)
	L = a[1:] + a[0]
	R = a[b - 1] + a[0:b - 1]
	if R == L:
		print('YES')
	else:
		print('NO')


def main(s):
	L = s[1:] + s[0:1]
	R = s[-1] + s[0:-1]
	if L == R:
		print('YES')
	else:
		print('NO')
for _ in range(int(input())):
	S = str(input())
	main(S)


for _ in range(int(input())):
	s = input()
	l = s[1:] + s[0]
	r = s[len(s) - 1] + s[:-1]
	if l == r:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	s = input()
	s1 = s[1:len(s)] + s[0]
	s2 = s[-1] + s[0:len(s) - 1]
	if s1 == s2 or s == s1 or s2 == s:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	s = input()
	ls = s[1:] + s[0]
	rs = s[-1] + s[0:-1]
	if ls == rs:
		print('YES')
	else:
		print('NO')


for _ in range(0, int(input())):
	a = input()
	l = a[1:] + a[0]
	r = a[-1] + a[0:-1]
	if l == r:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	s = input()
	a = s[1:] + s[0]
	b = s[len(s) - 1] + s[:len(s) - 1]
	if a == b:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	s = input()
	temp = s[1:] + s[0]
	if temp[1:] + temp[0] == s:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	a = input()
	if a[1:] + a[0] == a[-1] + a[:-1]:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	s = input()
	l = s[1:] + s[0]
	r = s[-1] + s[:-1]
	if l == r:
		print('YES')
	else:
		print('NO')


T = int(input())
for i in range(T):
	s = input()
	s1 = s[1:] + s[:1]
	s2 = s[-1:] + s[:-1]
	if s1 == s2:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	a = input()
	temp1 = a[1:] + a[0]
	temp2 = a[-1] + a[0:-1]
	if temp1 == temp2:
		print('YES')
	else:
		print('NO')


testcases = int(input())
i = 0
while i < testcases:
	y = input()
	temp1 = y[1:] + y[0]
	temp2 = y[-1] + y[0:-1]
	if temp1 == temp2:
		print('YES')
	else:
		print('NO')
	i = i + 1


for _ in range(int(input())):
	x = input()
	x1 = x[1:len(x)] + x[0]
	x2 = x[-1] + x[0:len(x) - 1]
	if x1 == x2 or x == x1 or x2 == x:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	s = input()
	n = len(s)
	ls = s[1:n] + s[0]
	rs = s[n - 1] + s[0:n - 1]
	if ls == rs:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	a = input()
	a1 = a[1:len(a)] + a[0]
	a2 = a[-1] + a[0:len(a) - 1]
	if a1 == a2 or a == a1 or a2 == a:
		print('YES')
	else:
		print('NO')


def l(s):
	try:
		l = s[1:] + s[0]
		r = s[-1] + s[:-1]
		if l == r:
			return 'YES'
		else:
			return 'NO'
	except:
		pass
t = int(input())
for i in range(t):
	print(l(input()))


for _ in range(int(input())):
	s = input()
	if s.count(s[0]) == len(s):
		print('YES')
	elif s.count(f'{s[0]}{s[1]}') == len(s) / 2:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	s = input()
	s1 = s[1:] + s[0]
	s2 = s[-1] + s[:-1]
	if s1 == s2:
		print('YES')
	else:
		print('NO')


numberOfTestCases = int(input())
for i in range(numberOfTestCases):
	x = 0
	string = input()
	listt = []
	leftShiftList = []
	rightShiftList = []
	for element in string:
		listt.append(element)
	lastElement = len(listt)
	for i in range(len(listt)):
		if i == lastElement - 1:
			leftShiftList.append(listt[0])
		else:
			leftShiftList.append(listt[i + 1])
	leftString = ''.join(leftShiftList)
	for i in range(len(listt)):
		if i == lastElement - 1:
			rightShiftList.append(listt[i - 1])
		else:
			rightShiftList.append(listt[x - 1])
		x = x + 1
	rightString = ''.join(rightShiftList)
	if rightString == leftString:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	n = input()
	k = n[-1:] + n[:-1]
	l = n[1:] + n[:1]
	if k == l:
		print('YES')
	else:
		print('NO')


def l(x):
	v = x[1:]
	s = x[0]
	v += s
	return v

def r(x):
	v = x[-1]
	s = x[:-1]
	s = v + s
	return s
n = int(input())
for i in range(n):
	x = input()
	if l(x) == r(x):
		print('YES')
	else:
		print('NO')


for I in range(int(input())):
	B = input()
	C = B[1:len(B)] + B[0]
	D = B[-1] + B[0:len(B) - 1]
	if C == D or B == C or D == B:
		print('YES')
	else:
		print('NO')


for i in range(0, int(input())):
	s = input()
	left = ''
	right = ''

	def Left(x, y):
		for j in range(1, len(x)):
			y = y + x[j]
		y = y + x[0]
		return y

	def Right(x, z):
		z = z + x[-1]
		for j in range(0, len(x) - 1):
			z = z + x[j]
		return z
	if Left(s, left) == Right(s, right):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	janu = input()
	vijay = janu[1:len(janu)] + janu[0]
	vj = janu[-1] + janu[0:len(janu) - 1]
	if vijay == vj or janu == vijay or vj == janu:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	x = str(input())
	if x[1:len(x)] + x[0] == x[-1] + x[0:len(x) - 1]:
		print('YES')
	else:
		print('NO')


def left(s):
	return s[1:] + s[0]

def right(s):
	return s[-1] + s[0:len(s) - 1]
for i in range(int(input())):
	s = input()
	if left(s) == right(s):
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	s = input()
	if s[1:] + s[0] == s[-1] + s[0:len(s) - 1]:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	a = input()
	if len(set(a)) == 1 or len(a) == 2:
		print('YES')
	elif a[1:] + a[0] == a[-1] + a[0:len(a) - 1]:
		print('YES')
	else:
		print('NO')


t = int(input())
for r in range(t):
	s = input()
	a = s[1:] + s[0]
	b = s[-1] + s[:-1]
	if a == b:
		print('YES')
	else:
		print('NO')


t = int(input())
while t > 0:
	s = input()
	ansl = s[1:] + s[0]
	ansr = s[-1] + s[:-1]
	if ansl == ansr:
		print('YES')
	else:
		print('NO')
	t -= 1


t = int(input())
while t > 0:
	s = []
	s = list(input())
	size = len(s)
	a = []
	b = []
	flag = 0
	for i in range(1, size):
		a.append(s[i])
	a.append(s[0])
	b.append(s[size - 1])
	for j in range(size - 1):
		b.append(s[j])
	for k in range(size):
		if a[k] != b[k]:
			flag = 1
	if flag == 0:
		print('YES')
	else:
		print('NO')
	t = t - 1


T = int(input())
for i in range(T):
	S = input()
	L = ''
	R = ''
	j = 0
	R += S[-1]
	for i in range(1, len(S)):
		L += S[i]
		R += S[i - 1]
	L += S[0]
	if S == L and S == R or L == R:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	s = input()
	sp = s[1:len(s)] + s[0]
	sk = s[-1] + s[:-1]
	if sp == sk:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	word = input()
	left = word[1:]
	left_one = word[0]
	lefty = left + left_one
	right = word[-1]
	right_one = word[:-1]
	righty = right + right_one
	if lefty == righty:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	w = input()
	wq = w[1:] + w[0]
	we = w[-1] + w[:-1]
	if we == wq:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	w = input()
	s = w[1:] + w[0]
	q = w[-1] + w[:-1]
	if s == q:
		print('YES')
	else:
		print('NO')


from collections import deque
t = int(input())
while t != 0:
	s = input()
	d = deque(s)
	d1 = deque(s)
	d.rotate(-1)
	d1.rotate(1)
	a = ''.join(d)
	b = ''.join(d1)
	if a == b:
		print('YES')
	else:
		print('NO')
	t -= 1


t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	l_s = s[1:] + s[0]
	r_s = s[-1] + s[:-1]
	if l_s == r_s:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	s = input()
	if len(s) == 1 or len(s) == 2 or len(set(s)) == 1:
		print('YES')
		continue
	if len(s) % 2 != 0:
		print('NO')
	else:
		x = s[0] + s[1]
		for j in range(2, len(s), 2):
			if s[j] + s[j + 1] != x:
				print('NO')
				break
		else:
			print('YES')


for i in range(int(input())):
	s = input()
	l = list(s)
	m = list(s)
	n = list(s)
	c = 0
	d = m.pop(0)
	m.append(d)
	d = n.pop()
	n.insert(0, d)
	for j in range(len(m)):
		if m[j] == n[j]:
			c = c + 1
	if c == len(l):
		print('YES')
	else:
		print('NO')


t = int(input())
while t > 0:
	s = input()
	p = len(s)
	s1 = ''
	s2 = ''
	for i in range(1, p):
		s1 += s[i]
	for i in range(0, 1):
		s1 += s[i]
	for i in range(p - 1, p):
		s2 += s[i]
	for i in range(0, p - 1):
		s2 += s[i]
	if s1 == s2:
		print('YES')
	else:
		print('NO')
	t -= 1


t = int(input())
for bunny in range(t):
	s = input()
	if s[1:len(s)] + s[0] == s[-1] + s[:len(s) - 1]:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	str_ = input()
	if len(str_) == 1:
		print('YES')
	else:
		strL = str_[-1] + str_[:len(str_) - 1]
		strR = str_[1:] + str_[0]
		if strR == strL:
			print('YES')
		else:
			print('NO')


t = int(input())
while t > 0:
	s = input()
	l = s[1:] + s[0]
	v = s[-1] + s[:-1]
	if l == v:
		print('YES')
	else:
		print('NO')
	t = t - 1


for _ in range(int(input())):
	S = input()
	S1 = S[1:] + S[0]
	S2 = S[-1] + S[:-1]
	if S1 == S2:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	s = input()
	R = s[-1] + s[:len(s) - 1]
	L = s[1:] + s[0]
	if R == L:
		print('YES')
	else:
		print('NO')


def ls(s):
	l = list(s)
	l.append(l[0])
	l.remove(l[0])
	st = ''
	for i in l:
		st += i
	return st

def rs(s):
	li = list(s)
	li.insert(0, li[-1])
	li.pop()
	st = ''
	for x in li:
		st += x
	return st
n = int(input())
for i in range(0, n):
	s = input()
	if len(s) == 1:
		print('YES')
	else:
		a = ls(s)
		b = rs(s)
		if a == b:
			print('YES')
		else:
			print('NO')


def leftshift(s):
	n = len(s)
	lis = list(s)
	for i in range(0, n - 1):
		lis[i] = lis[i + 1]
	lis[n - 1] = s[0]
	return ''.join(lis)

def rightshift(s):
	n = len(s)
	lis = list(s)
	for i in range(n - 1, 0, -1):
		lis[i] = lis[i - 1]
	lis[0] = s[n - 1]
	return ''.join(lis)
for _ in range(int(input())):
	s = input()
	if leftshift(s) == rightshift(s):
		print('YES')
	else:
		print('NO')