You want to type the string $s$, consisting of $n$ lowercase Latin letters, using your favorite text editor Notepad#.

Notepad# supports two kinds of operations:

append any letter to the end of the string;

copy a continuous substring of an already typed string and paste this substring to the end of the string.

Can you type string $s$ in strictly less than $n$ operations?


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.

The first line of each testcase contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of the string $s$.

The second line contains a string $s$, consisting of $n$ lowercase Latin letters.

The sum of $n$ doesn't exceed $2 \cdot 10^5$ over all testcases.


-----Output-----

For each testcase, print "YES" if you can type string $s$ in strictly less than $n$ operations. Otherwise, print "NO".


-----Examples-----

Input
6
10
codeforces
8
labacaba
5
uohhh
16
isthissuffixtree
1
x
4
momo
Output
NO
YES
NO
YES
NO
YES


-----Note-----

In the first testcase, you can start with typing "codef" ($5$ operations), then copy "o" ($1$ operation) from an already typed part, then finish with typing "rces" ($4$ operations). That will be $10$ operations, which is not strictly less than $n$. There exist other ways to type "codeforces". However, no matter what you do, you can't do less than $n$ operations.

In the second testcase, you can type "labac" ($5$ operations), then copy "aba" ($1$ operation), finishing the string in $6$ operations.

Difficulty: EASY
Tags: Implementation

Starter code:

Solutions:
def main():
	import sys
	input = sys.stdin.readline
	for i in range(int(input())):
		n = int(input())
		s = input()
		pary = set()
		result = False
		poprzednia = ''
		for j in range(n - 1):
			para = s[j:j + 2]
			if para in pary:
				result = True
				break
			pary.add(poprzednia)
			poprzednia = para
		sys.stdout.write('YES\n' if result == True else 'NO\n')
main()


import sys
input = sys.stdin.readline

def print_str_line(str):
	sys.stdout.write(str + '\n')

def print_number(number):
	print_str_line(f'{number}')

def ans(string, number_of_operations):
	set_pair = set()
	tmp_pair = string[0:2]
	for i in range(1, len(string) - 1):
		curr_pair = string[i:i + 2]
		if string[i:i + 2] in set_pair:
			return True
		set_pair.add(tmp_pair)
		tmp_pair = curr_pair
	return False
number_of_inputs = int(input())
for i in range(number_of_inputs):
	number_of_operations = int(input())
	string_to_type = input()
	_ans = ans(string_to_type, number_of_operations)
	if _ans:
		print('YES')
	else:
		print('NO')


def solve(s, n):
	my_set = {}
	for i in range(n - 1):
		substr = s[i:i + 2]
		if substr in my_set and i - my_set[substr] > 1:
			return 'YES'
		elif substr not in my_set:
			my_set[substr] = i
	return 'NO'

def main():
	t = int(input())
	while t > 0:
		n = int(input())
		s = input()
		print(solve(s, n))
		t -= 1
main()


import math
from collections import *

def solve():
	n = int(input())
	a = input()
	d = defaultdict(int)
	for i in range(0, n - 1):
		s = ''
		s += a[i]
		s += a[i + 1]
		if s in d and d[s] != i - 1:
			print('YES')
			return
		elif s not in d:
			d[s] = i
	print('NO')
t = int(input())
for _ in range(t):
	solve()


T = int(input())
for t in range(T):
	n = int(input())
	s = input()
	flag = True
	book = {}
	for i in range(n - 1):
		t = s[i:i + 2]
		if t in book:
			if book[t] < i - 1:
				print('YES')
				flag = False
				break
		else:
			book[t] = i
	if flag:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	s = input()
	cur = {}
	for i in range(n - 1):
		t = s[i:i + 2]
		if t in cur:
			if cur[t] < i - 1:
				print('YES')
				break
		else:
			cur[t] = i
	else:
		print('NO')


AmZx = int(input())
AcbUyhBttt = 0
for j in range(AmZx):
	AmZx1 = int(input())
	AmZx2 = input()
	cur = {}
	for i in range(AmZx1 - 1):
		AmZx = AmZx2[i:i + 2]
		if AmZx in cur:
			if cur[AmZx] < i - 1:
				print('YES')
				break
		else:
			cur[AmZx] = i
	else:
		print('NO')


def solution():
	n = int(input())
	s = input()
	if n <= 3:
		print('NO')
		return
	d = {s[0:2]}
	for i in range(2, n - 1):
		if s[i:i + 2] in d:
			print('YES')
			return
		d.add(s[i - 1:i + 1])
	print('NO')

def main():
	t = int(input())
	while t:
		solution()
		t -= 1
main()


t = int(input())

def solve(n, string):
	s = {}
	for i in range(0, len(string) - 1):
		sub = string[i:i + 2]
		if sub in s and s[sub] <= i - 2:
			return 'YES'
		if sub not in s:
			s[sub] = i
	return 'NO'
for i in range(t):
	n = int(input())
	string = input()
	print(solve(n, string))


def codeforces():
	san = int(input())
	for i in range(san):
		n = int(input())
		a = input()
		d = {}
		c = 0
		for i in range(n - 1):
			if a[i] + a[i + 1] not in d:
				d[a[i] + a[i + 1]] = i + 1
			elif d[a[i] + a[i + 1]] != i:
				c = 1
				break
		if c == 1:
			print('YES')
		else:
			print('NO')
codeforces()


def solve(n, s):
	sef = set()
	for i in range(1, len(s) - 2):
		sef.add(s[i - 1] + s[i])
		if s[i + 1] + s[i + 2] in sef:
			print('YES')
			return
	print('NO')
no_prb = int(input())
prb = []
for i in range(no_prb):
	prb.append((int(input()), input()))
for each in prb:
	solve(each[0], each[1])


def func(size: int, s: str):
	d = {}
	for i in range(0, size - 1):
		if s[i:i + 2] not in d:
			d[s[i:i + 2]] = i
		elif i == d[s[i:i + 2]] + 1:
			continue
		else:
			return True
	return False
t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	if func(n, s):
		print('YES')
	else:
		print('NO')


import math
for _ in range(int(input())):
	n = int(input())
	s = input()
	mp = {}
	ans = 'NO'
	for i in range(len(s) - 1):
		x = s[i]
		x += s[i + 1]
		if x not in mp:
			mp[x] = i
		elif mp[x] != i - 1:
			ans = 'YES'
			break
	print(ans)


for i in range(int(input())):
	n = int(input())
	st = input()
	d = {}
	for j in range(n - 1):
		temp = st[j:j + 2]
		if temp not in d:
			d[temp] = j
		elif d[temp] < j - 1:
			print('YES')
			break
	else:
		print('NO')


tc = int(input())
for _ in range(tc):
	n = int(input())
	s = input()
	tr = {}
	c = n - 1
	for i in range(c):
		j = s[i:i + 2]
		if j in tr:
			if tr[j] < i - 1:
				print('YES')
				break
		else:
			tr[j] = i
	else:
		print('NO')


def solve():
	l = int(input())
	s = input()
	for i in range(1, len(s)):
		if s[i - 1] + s[i] in s[i + 1:]:
			print('YES')
			return
	else:
		print('NO')
		return
t = int(input())
while t != 0:
	solve()
	t -= 1


import os
import math
import collections
import bisect
import functools
import itertools
import string

def solve(s, n):
	d = {}
	for i in range(n - 1):
		sub = s[i] + s[i + 1]
		if sub in d:
			if i - d[sub] > 1:
				return True
		else:
			d[sub] = i
	return False
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	ok = solve(s, n)
	if ok:
		print('YES')
	else:
		print('NO')


import sys
input = sys.stdin.readline

def sol(n, s):
	st = set()
	for i in range(1, n - 1):
		if s[i:i + 2] in st:
			return 'YES'
		st.add(s[i - 1:i + 1])
	return 'NO'
t = int(input())
for case in range(t):
	n = int(input())
	s = input()
	print(sol(n, s))


t = int(input())
for i in range(t):
	x = int(input())
	s = input()
	if x > len(s):
		print('YES')
	else:
		temp = ''
		z = ''
		key = 0
		ans = len(s)
		for y in s:
			if z + y in temp:
				ans -= 1
				z += y
			else:
				temp += z
				z = y
			if ans < x:
				key = 1
				break
		if key == 1:
			print('YES')
		else:
			print('NO')


check = {}

def tinh(st):
	for i in range(0, n - 1):
		if st[i:i + 2] in check:
			if check[st[i:i + 2]] + 1 < i:
				return 'YES'
		else:
			check[st[i:i + 2]] = i
	return 'NO'
t = int(input())
for i in range(t):
	n = int(input())
	st = input()
	print(tinh(st))
	check.clear()


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	d = {}
	found = False
	a = s[0:2]
	d[a] = 1
	prev = a
	prevtoprev = '12'
	for i in range(1, n - 1):
		prev = a
		a = s[i:i + 2]
		if prevtoprev == a:
			found = True
			break
		elif prev == a:
			prevtoprev = a
			continue
		if a not in d:
			d[a] = 1
		else:
			found = True
			break
	if found:
		print('YES')
	else:
		print('NO')


def solve():
	n = int(input())
	s = input()
	dt = {}
	for i in range(1, len(s)):
		ch = s[i - 1] + s[i]
		if ch in dt:
			print('YES')
			return
		if i - 2 >= 0:
			c = s[i - 2] + s[i - 1]
			dt[c] = 1
	print('NO')
test = int(input())
for i in range(test):
	solve()


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	seen = set()
	ans = False
	prev = ''
	for i in range(1, n):
		characters = s[i - 1:i + 1]
		if characters in seen:
			ans = True
			break
		seen.add(prev)
		prev = characters
	if ans:
		print('YES')
	else:
		print('NO')


t = int(input())
while t > 0:
	n = int(input())
	s = input()
	curr = dict()
	flag = False
	for i in range(n):
		temp = s[i:i + 2]
		if temp in curr:
			if curr[temp] < i - 1:
				flag = True
				break
		else:
			curr[temp] = i
	if flag:
		print('YES')
	else:
		print('NO')
	t -= 1


def helper(word):
	store = set()
	prev = ''
	for i in range(1, len(word)):
		cur = word[i - 1] + word[i]
		if cur in store:
			return 'YES'
		store.add(prev)
		prev = cur
	return 'NO'
length = int(input())
for _ in range(length):
	n = int(input())
	word = input()
	print(helper(word))


def solution():
	n = int(input())
	s = input()
	if n <= 3:
		print('NO')
		return
	mySet = {s[0:1]}
	for i in range(3, n + 1):
		if s[i - 2:i] in mySet:
			print('YES')
			return
		mySet.add(s[i - 3:i - 1])
	print('NO')
t = int(input())
for i in range(t):
	solution()


from collections import defaultdict, Counter
from os import path
import sys
from collections import defaultdict
import math

def int_inp():
	return int(input())

def mul_inp():
	return map(int, input().split())

def arr_inp():
	return list(map(int, input().split()))

def is_prime(n):
	prime_flag = 0
	if n > 1:
		for i in range(2, int(math.sqrt(n)) + 1):
			if n % i == 0:
				prime_flag = 1
				break
		if prime_flag == 0:
			return True
		else:
			return False
	else:
		return False

def factors(x):
	result = []
	i = 1
	while i * i <= x:
		if x % i == 0:
			result.append(i)
			if x // i != i:
				result.append(x // i)
		i += 1
	return result

def prime_factors(x):
	result = []
	i = 1
	while i * i <= x:
		if x % i == 0:
			result.append(i)
		i += 1
	return result

def solution():
	n = int_inp()
	s = input()
	if n == 1:
		print('NO')
		return
	for i in range(n - 2):
		if s[i:i + 2] in s[i + 2:]:
			print('YES')
			return
	print('NO')
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
for _ in range(int_inp()):
	x = solution()


import math
t = int(input())
for j in range(t):
	n = int(input())
	s = input()
	m = False
	if len(s) > 3:
		for i in range(n - 1):
			if s[i:i + 2] in s[i + 2:]:
				m = True
				break
		if m:
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


t = int(input())
while t > 0:
	n = int(input())
	s = input()
	if len(s) <= 3:
		print('NO')
	else:
		see = set()
		init = s[0] + s[1]
		see.add(init)
		pre = s[1] + s[2]
		sign = 0
		for i in range(2, len(s) - 1):
			temp = s[i] + s[i + 1]
			if temp in see:
				sign = 1
				break
			see.add(pre)
			pre = temp
		if sign:
			print('YES')
		else:
			print('NO')
	t -= 1


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	d = {}
	ans = 'NO'
	for i in range(1, len(s) - 2):
		pair = (s[i - 1], s[i])
		d[pair] = 1
		if (s[i + 1], s[i + 2]) in d:
			ans = 'YES'
			break
	print(ans)


def is_less_than_n_operations(s):
	for i in range(len(s) - 1):
		if s[i:i + 2] in s[i + 2:]:
			return 'YES'
	return 'NO'
t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	print(is_less_than_n_operations(s))


for _ in range(int(input())):
	n = int(input())
	s = input()
	d = {}
	i = 0
	while i < n - 1:
		temp = s[i] + s[i + 1]
		if temp in d:
			if d[temp] != i:
				print('YES')
				break
		else:
			d[temp] = i + 1
		i += 1
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	s = input()
	dic = {}
	ans = 'NO'
	for i in range(n - 1):
		s1 = s[i] + s[i + 1]
		if s1 in dic:
			if i - dic[s1] >= 2:
				ans = 'YES'
				break
		else:
			dic[s1] = i
	print(ans)


def sol():
	n = int(input())
	s = input()
	for i in range(2, n - 1):
		if s[i:i + 2] in s[:i]:
			print('YES')
			return
	print('NO')
	return
for i in range(int(input())):
	sol()


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	if n <= 3:
		print('NO')
		continue
	stop = 0
	for i in range(n - 2):
		if s[i:i + 2] in s[i + 2:]:
			stop = 1
			break
	if stop == 0:
		print('NO')
	else:
		print('YES')


import sys
import re
import math
from math import log2
from math import log
from math import ceil
from math import gcd
from decimal import *
from collections import deque
import random
import heapq
import itertools
import datetime
const = 1000000007
ep = 1e-08

def get():
	return list(map(int, input().split()))
n = int(input())
for i in range(n):
	m = int(input())
	line = input()
	d = {}
	found = False
	for i in range(m - 1):
		temp = line[i:i + 2]
		if temp in d:
			if d[temp] != i - 1:
				found = True
				break
		if temp not in d:
			d[temp] = i
	if found:
		print('YES')
	else:
		print('NO')


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	res = False
	pos = {}
	for i in range(n - 1):
		if s[i:i + 2] not in pos:
			pos[s[i:i + 2]] = i + 1
		elif pos[s[i:i + 2]] < i:
			res = True
			break
	print('YES' if res else 'NO')


import math
for _ in range(int(input())):
	n = int(input())
	s = input()
	di = {}
	f = 0
	for i in range(1, n):
		s1 = s[i - 1] + s[i]
		if s1 in di and di[s1] != i - 1:
			f = 1
			break
		elif s1 not in di:
			di[s1] = i
	if f == 0:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	s = input()
	mp = dict()
	ans = 'NO'
	for i in range(1, n):
		pp = s[i - 1:i + 1]
		if pp in mp and mp[pp] != i - 1:
			ans = 'YES'
			break
		elif pp not in mp:
			mp[pp] = i
	print(ans)


from collections import deque
import sys
input = sys.stdin.readline
K = int(input())
for _ in range(K):
	n = int(input())
	queue = deque()
	word = input().rstrip()
	if len(word) <= 3:
		print('NO')
		continue
	a = 0
	for i in range(len(word) - 2):
		if word[i:i + 2] in word[i + 2:]:
			a = 1
			break
	if a == 1:
		print('YES')
	else:
		print('NO')


def op_string(s, n):
	ans = 'NO'
	if n > 3:
		for i in range(n - 2):
			subs = s[i:i + 2]
			if s.find(subs, i + 2) != -1:
				ans = 'YES'
				break
	return ans
T = int(input())
for t in range(T):
	n = int(input())
	s = input()
	print(op_string(s, n))


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	pairs = set()
	dop = ''
	for i in range(n - 1):
		ch = s[i] + s[i + 1]
		if ch in pairs:
			print('YES')
			break
		else:
			pairs.add(dop)
			dop = ch
	else:
		print('NO')


import sys

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

def in_str():
	return sys.stdin.readline().rstrip()

def in_map_int():
	return map(int, sys.stdin.readline().split())

def in_arr_int():
	return list(map(int, sys.stdin.readline().split()))

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

def is_prime(n):
	for i in range(2, int(n ** (1 / 2)) + 1):
		if n % i == 0:
			return True
	return False

def solve(n, s):
	i = 0
	c = ''
	while i + 1 < n:
		if s[i:i + 2] in c:
			return 'YES'
		else:
			c += s[i]
		i += 1
	return 'NO'

def main():
	t = in_int()
	for _ in range(t):
		n = in_int()
		s = in_str()
		print(solve(n, s))
main()


for _ in range(int(input())):
	n = int(input())
	s = input()
	flag = 1
	for i in range(0, n - 1):
		if s[i:i + 2] in s[0:i]:
			print('YES')
			flag = 0
			break
	if flag == 1:
		print('NO')


for i in range(int(input())):
	n = int(input())
	s = input()
	if n == 1:
		print('NO')
	else:
		flag = 0
		for i in range(n - 2, -1, -1):
			a = s[i:i + 2]
			if a in s[:i]:
				if i - s.index(a) >= 2:
					flag = 1
					break
		if flag == 1:
			print('YES')
		else:
			print('NO')


for i in range(int(input())):
	n = int(input())
	x = input()
	c = 'NO'
	for j in range(n - 1):
		if x[j] + x[j + 1] in x[j + 2:]:
			c = 'YES'
			break
	print(c)


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	count = 0
	if n <= 3:
		print('NO')
		count = 2
	else:
		a = set()
		a.add(s[:2])
		for j in range(2, n - 1):
			if s[j:j + 2] in a:
				print('YES')
				count = 1
				break
			else:
				a.add(s[j - 1:j + 1])
	if count == 0:
		print('NO')


def verdict(n, s):
	for i in range(n - 1):
		if s[i:i + 2] in s[:i]:
			return 'YES'
	return 'NO'
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	print(verdict(n, s))


for tests in range(int(input())):
	n = int(input())
	s = input()
	d = {}
	for i in range(n - 1):
		t = s[i:i + 2]
		try:
			d[t]
			if d[t] < i - 1:
				print('YES')
				break
		except:
			d[t] = i
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	st = set()
	fg = 0
	for j in range(n - 1):
		if s[j:j + 2] in st:
			fg = 1
			break
		if j > 0:
			st.add(s[j - 1:j + 1])
	if fg:
		print('YES')
	else:
		print('NO')


t = int(input())
result = []
for i in range(t):
	n = int(input())
	s = input()
	if n < 3:
		result.append('NO')
	else:
		temp = 'NO'
		for j in range(0, n - 1):
			if s[j:j + 2] in s[j + 2:]:
				temp = 'YES'
				break
		result.append(temp)
print(*result, sep='\n')


input_count = int(input())
output = ''
for _ in range(input_count):
	len_word = int(input())
	word = input()[0:len_word]
	eq = False
	for i in range(len(word) - 3):
		if word[i:i + 2] in word[i + 2:]:
			eq = True
			break
	output += 'YES\n' if eq else 'NO\n'
print(output[:-1])


def find_duplicate(word, n):
	h = dict()
	i = 0
	while i < n:
		if word[i:i + 2] not in h.keys():
			h[word[i:i + 2]] = [1, i]
		elif i - h[word[i:i + 2]][1] >= 2:
			return 'YES'
		i += 1
	return 'NO'

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		word = input()
		print(find_duplicate(word, n))
main()


def solve(n, r):
	for i in range(n - 1):
		cur = r[i] + r[i + 1]
		oth = r.find(cur)
		if oth != i:
			if oth != i - 1:
				return 'YES'
	return 'NO'
n = int(input())
for i in range(n):
	print(solve(int(input()), input()))


for _ in range(int(input())):
	n = int(input())
	s = input()
	b = False
	if n == 1 or n == 2 or n == 3:
		print('NO')
		continue
	for i in range(n - 3):
		if s[i:i + 2] in s[i + 2:]:
			b = True
			break
	if b:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	flag = False
	d = {}
	for j in range(len(s)):
		if s[j:j + 2] in d:
			if d[s[j:j + 2]][1] != j:
				flag = True
				break
		else:
			d[s[j:j + 2]] = (j, j + 1)
	if flag:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	s = input()
	d = {}
	b = 0
	for i in range(n - 1):
		s1 = s[i] + s[i + 1]
		if d.get(s1) != None:
			if d[s1] != i - 1:
				b = 1
				break
		else:
			d[s1] = i
	if b == 1:
		print('YES')
	else:
		print('NO')


t = int(input())
import math
for ii in range(t):
	n = int(input())
	dd = {}
	s = input()
	kk = False
	i = 0
	while i < n - 1:
		gg = s[i] + s[i + 1]
		if gg in dd and dd[gg] != i - 1:
			kk = True
			break
		if gg not in dd:
			dd[gg] = i
		i += 1
	if kk:
		print('YES')
	else:
		print('NO')


from collections import defaultdict

def solve(n, s):
	d = defaultdict(lambda : -1)
	for i in range(n - 1):
		if d[s[i:i + 2]] != -1:
			if d[s[i:i + 2]] < i - 1:
				return 'YES'
		else:
			d[s[i:i + 2]] = i
	return 'NO'
for _ in range(int(input())):
	n = int(input())
	s = input()
	print(solve(n, s))


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	f = set()
	check = False
	for i in range(n - 1):
		if s[i] + s[i + 1] in f:
			check = True
			break
		if i != 0:
			f.add(s[i - 1] + s[i])
	if check:
		print('YES')
	else:
		print('NO')


testcase_no = int(input())
for _ in range(testcase_no):
	flag = False
	length = int(input())
	word = input()
	list_of_substrings = dict()
	for i in range(length - 1):
		segment = word[i:i + 2]
		if segment in list_of_substrings.keys():
			if i - 1 != list_of_substrings[segment]:
				print('YES')
				flag = True
				break
		else:
			list_of_substrings[word[i:i + 2]] = i
	if not flag:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	d = {}
	flag = 0
	for i in range(n - 1):
		p = s[i:i + 2]
		r = str(i + 1)
		if p not in d:
			d[p] = r
		elif d[p] != str(i):
			flag = 1
			break
	if flag == 0:
		print('NO')
	else:
		print('YES')