Read problems statements in [Hindi], [Mandarin Chinese], [Russian], [Vietnamese] and [Bengali] as well.

Chef wants to prepare a special dish. There is a special ingredient Chef needs for this dish, so he decided to search for it in all of Chefland. After some research, he discovered it in a secret cave. He may only enter the cave if he has a password; fortunately, a string $S$, which serves as a hint for this password, is written next to the cave.

Chef knows that the secret password is a non-empty prefix of the string $S$. Also, he knows that:
if a prefix occurs in $S$ more often as a substring, then the probability that this prefix is the secret password is higher (the probability that a chosen prefix is the secret password is an increasing function of its number of occurrences in $S$)
if two prefixes have the same number of occurrences in $S$, then the longer prefix has a higher probability of being the secret password

Chef wants to guess the secret password with the maximum possible probability of success. Help Chef and find the prefix for which this probability is maximum.

------  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 single integer $N$.
The second line contains a single string $S$ with length $N$.

------  Output ------
For each test case, print a single line containing one string — the prefix with the highest probability of being the secret password.

------  Constraints ------
$1 ≤ T ≤ 100$
$1 ≤ N ≤ 100,000$
$S$ contains only lowercase English letters

----- Sample Input 1 ------ 
3
3
abc
5
thyth
5
abcbc
----- Sample Output 1 ------ 
abc
th
abcbc
----- explanation 1 ------ 
Example case 1: Each prefix occurs in $S$ the same number of times (once) and the prefix with maximum length is "abc", so the secret password is most likely "abc".

Difficulty: HARD
Tags: Constructive algorithms

String algorithms

Sorting

Complete search

Data structures

Ad-hoc
Skill types: Sorting

Data structures

Complete search

Starter code:

Solutions:
for tea in range(int(input())):
	n = int(input())
	s = input()
	inds = []
	for i in range(n):
		if s[i] == s[0]:
			inds.append(i)
	good = 1
	while True:
		sobad = False
		for i in inds:
			if i + good >= n:
				sobad = True
				break
			if s[i + good] != s[good]:
				sobad = True
				break
		if sobad:
			break
		good += 1
		if good == n:
			break
	print(s[:good])


for t in range(int(input())):
	n = int(input())
	s = input()
	candidates = set()
	count = 0
	for i in range(1, n):
		if s[i] == s[count] and s[i - count] == s[0]:
			candidates.add(i)
	if len(candidates) == 0:
		print(s)
	else:
		candidates = list(candidates)
		lc = len(candidates)
		ans = s[0]
		for i in range(1, n):
			count1 = 0
			for (j, c) in enumerate(candidates):
				if c != n - 1 and s[c + 1] == s[i]:
					candidates[j] = c + 1
					count1 += 1
			if count1 == lc:
				ans += s[i]
			else:
				break
		print(ans)


for t in range(int(input())):
	n = int(input())
	s = input()
	candidates = []
	count = 0
	for i in range(n):
		if s[i] == s[0]:
			candidates.append(i)
			count += 1
	if count == 1:
		print(s)
	else:
		ans = s[0]
		for i in range(1, n):
			count1 = 0
			for (j, c) in enumerate(candidates):
				if c != n - 1 and s[c + 1] == s[i]:
					candidates[j] = c + 1
					count1 += 1
			if count1 == count:
				ans += s[i]
			else:
				break
		print(ans)


for z in range(int(input())):
	N = int(input())
	S = str(input())
	count = 0
	ls = []
	new_string = S[0]
	for i in range(N):
		if new_string == S[i]:
			ls.append(i)
			count += 1
	if count == 1:
		print(S)
	else:
		check = True
		for i in range(1, N + 1):
			count_1 = 0
			for (k, j) in enumerate(ls):
				if j != N - 1 and S[i] == S[j + 1]:
					count_1 += 1
					ls[k] = j + 1
			if count_1 == count:
				new_string += S[i]
			else:
				break
		print(new_string)


for _ in range(int(input())):
	n = int(input())
	s = input()
	new_string = s[0]
	l = []
	count_1 = 0
	for i in range(n):
		if s[i] == new_string:
			l.append(i)
			count_1 += 1
	for i in range(1, n):
		count_2 = 0
		l1 = []
		for j in l:
			if j != n - 1 and s[j + 1] == s[i]:
				count_2 += 1
				l1.append(j + 1)
		l = l1
		if count_1 == count_2:
			new_string += s[i]
		else:
			break
	print(new_string)


def snek(s, n):
	x = s[0]
	k = []
	n2 = 0
	for i in range(n):
		if s[i] == x:
			k.append(i)
			n2 += 1
	for j in range(1, n):
		c = 0
		k1 = []
		for z in k:
			if z != n - 1 and s[z + 1] == s[j]:
				c += 1
				k1.append(z + 1)
		k = k1
		if n2 == c:
			x += s[j]
		else:
			break
	return x
t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	print(snek(s, n))


from math import *
import sys

def input():
	return sys.stdin.readline().replace('\n', '').strip()
sys.setrecursionlimit(10 ** 9)
for _ in range(int(input())):
	n = int(input())
	s = input()
	s1 = ''
	l = range(1, n)
	l3 = []
	pre_count = -1
	for i in range(n):
		s1 = s1 + s[i]
		count = 1
		len_str = i + 1
		l1 = []
		for j in l:
			if j + len_str - 1 < n and s[j + len_str - 1] == s1[-1]:
				count += 1
				l1.append(j)
		if pre_count > count:
			print(s1[:-1])
			break
		elif i == n - 1:
			print(s1)
			break
		pre_count = count
		l = list(l1)


def pass_word(s, n):
	strn = s[0]
	indx = []
	num = 0
	for i in range(n):
		if s[i] == strn:
			indx.append(i)
			num += 1
	for i in range(1, n):
		count = 0
		indx1 = []
		for j in indx:
			if j != n - 1 and s[j + 1] == s[i]:
				count += 1
				indx1.append(j + 1)
		indx = indx1
		if num == count:
			strn = strn + s[i]
		else:
			break
	return strn
t = int(input())
for x in range(t):
	N = int(input())
	S = input()
	result = pass_word(S, N)
	print(result)


def sol(s, n):
	c = 1
	l = []
	for i in range(n):
		if s[i] == s[0]:
			l.append(i)
	while 1:
		if c >= n:
			break
		for i in range(len(l)):
			if l[i] + 1 >= n:
				return c - 1
			if s[l[i] + 1] == s[c]:
				l[i] += 1
			else:
				return c - 1
		c += 1
	return n - 1
for _ in range(int(input())):
	n = int(input())
	s = input()
	print(s[:sol(s, n) + 1])


for _ in range(int(input())):
	n = int(input())
	S = input()
	X = []
	for _ in range(n):
		if S[_] == S[0]:
			X.append(_)
	x = len(X)
	if x == 1:
		print(S)
		continue
	for _ in range(0, X[1] + 1):
		for __ in range(x):
			if n <= X[__] + _:
				break
			if S[X[__] + _] != S[_]:
				break
		else:
			continue
		break
	print(S[:_])


T = int(input())
for i in range(T):
	n = int(input())
	st = input()
	s = set(st.split(st[0]))
	counter = st.count(st[0])
	a = st[0]
	for j in s:
		c = st.count(st[0] + j)
		if c == counter:
			if len(a) < len(st[0] + j):
				a = st[0] + j
	print(a)


from sys import stdin
input = stdin.readline

def answer():
	pos = [i for i in range(n)]
	(m, ans, st) = (-1000000000.0, '', '')
	for ch in s:
		st += ch
		x = []
		for i in pos:
			if i + 1 < n and s[i + 1] == ch:
				x.append(i + 1)
		if m <= len(x):
			m = len(x)
			ans = st
		else:
			break
		pos = x
	return ans
for T in range(int(input())):
	n = int(input())
	s = input()[:n]
	print(answer())


test = int(input())
for _ in range(test):
	n = int(input())
	s = input()
	if len(s) == 1:
		print(s)
		continue
	(first, counts, cur_len) = (s[0], [], 1)
	for i in range(n):
		if s[i] == first:
			counts.append(i)
	if len(counts) == 1:
		print(s)
		continue
	while True:
		for i in range(len(counts) - 1):
			if counts[i] + cur_len >= n or counts[i + 1] + cur_len >= n:
				break
			if s[counts[i] + cur_len] != s[counts[i + 1] + cur_len]:
				break
		else:
			cur_len += 1
			continue
		break
	print(s[:cur_len])


for _ in range(int(input())):
	n = int(input())
	s = input()
	l = [s[0]]
	m = n
	j = n
	for i in range(1, n):
		if s[i] == l[0]:
			j = i
			m = i
			break
		l.append(s[i])
	temp = 0
	for i in range(j, n):
		if s[i] == l[temp]:
			temp = temp + 1
			if temp == j:
				temp = 0
		else:
			if temp < m and temp != 0:
				m = temp
				if m == 1:
					break
			temp = 0
	if temp < m and temp != 0:
		m = temp
	for i in range(m):
		print(l[i], end='')
	print()


for _ in range(int(input())):
	n = int(input())
	s = input()
	first = s.count(s[0])
	if first == 1:
		print(s)
	else:
		low = 1
		high = n // first + 1
		flag = False
		i = 0
		while i < 100:
			mid = (low + high) // 2
			if low == high:
				break
			v = s.count(s[:mid])
			if v < first:
				high = mid
			else:
				low = mid
			if low + 1 == high:
				if s.count(s[:low]) > s.count(s[:high]):
					mid = low
				else:
					mid = high
				break
			i += 1
		print(s[:mid])


for _ in range(int(input())):
	n = int(input())
	s = input()
	l = s[0]
	ind = []
	for i in range(len(s)):
		if s[i] == l:
			ind.append(i)
	else:
		fl = 0
		ans = 1
		for i in range(n):
			for k in ind[1:]:
				if k + i >= n:
					fl = 1
				elif s[k + i] != s[i]:
					fl = 1
				if fl:
					break
			if fl:
				break
			ans += 1
		print(''.join(s[:ans - 1]))


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	if s.count(s[0]) == 1:
		print(s)
	else:
		max = 0
		res = ''
		ans = set(s.split(s[0]))
		for j in ans:
			if s.count(s[0] + j) >= max:
				max = s.count(s[0] + j)
				res = s[0] + j
		print(res)


ts = int(input())
while ts > 0:
	n = int(input())
	st = input()
	pos = []
	for i in range(1, len(st)):
		if st[i] == st[0]:
			pos.append(i)
	check = 1
	flag = True
	while check < n:
		for i in pos:
			if i + check > n - 1 or st[i + check] != st[check]:
				flag = False
				break
		if not flag:
			break
		check += 1
	print(st[0:check])
	ts -= 1


import math
import collections
from collections import defaultdict
x = int(input())
for _ in range(x):
	n = int(input())
	a = input()
	i = 1
	j = 0
	p = ''
	s = set()
	d = defaultdict(int)
	l = ''
	while i < n:
		if a[i] == a[j]:
			if len(p) >= 1:
				if p[0] == a[i]:
					j = 0
					p = ''
			p += a[i]
			s.add(p)
			if d[p] == 0:
				d[p] += 2
			else:
				d[p] += 1
			j += 1
			i += 1
		else:
			if j == 0:
				i += 1
			j = 0
			p = ''
			if i >= n:
				break
			if a[i] == a[j]:
				p += a[i]
				s.add(p)
				d[p] += 1
				j += 1
				i += 1
			else:
				i += 1
	k = 1
	lol = a
	for i in s:
		if (d[i] > k or (d[i] == k and len(i) > len(lol))) and i != '':
			k = d[i]
			lol = i
	print(lol)


for i1 in range(0, int(input())):
	n = int(input())
	s = input()
	a = s.count(s[0])
	we = len(s) // a
	for i in range(we):
		if s.count(s[0:we - i]) == a:
			print(s[0:we - i])
			break


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	s = input()
	if len(s) == 1:
		print(s)
		continue
	part = s.split(s[0])
	if len(part) == 2:
		print(s)
		continue
	part = set(part)
	if '' in part:
		part.remove('')
	pre = '' + s[0]
	i = 0
	flag = True
	while True:
		for item in part:
			if i >= len(item) or item[i] != s[i + 1]:
				flag = False
				break
		if not flag:
			break
		i += 1
		pre += s[i]
	if s.count(pre) == s.count(s[0]):
		print(pre)
	else:
		print(s[0])


try:
	test = int(input())
	while test > 0:
		n = int(input())
		s = input()
		l = set(s.split(s[0]))
		m = 0
		ans = s
		for i in l:
			k = s.count(s[0] + i)
			if k >= m:
				m = k
				ans = s[0] + i
		print(ans)
		test -= 1
except:
	pass


T = int(input())
for testcase in range(T):
	N = int(input())
	text = input()
	start = 1
	end = N
	dictCount = {}
	i = start
	while i < end:
		c = 0
		count = 0
		j = i
		while i < end and c < j and (text[i] == text[c]):
			i += 1
			c += 1
			if c not in dictCount:
				dictCount[c] = 1
			else:
				dictCount[c] += 1
		if c == 0:
			i += 1
	maxLen = -1
	maxCount = 0
	for k in dictCount:
		if dictCount[k] > maxCount:
			maxCount = dictCount[k]
			maxLen = k
		elif dictCount[k] == maxCount:
			if k > maxLen:
				maxCount = dictCount[k]
				maxLen = k
	if text[0] not in text[1:]:
		print(text)
	else:
		print(text[:maxLen])


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	indices = []
	for i in range(len(s)):
		if s[i] == s[0]:
			indices.append(i)
	maximum_possible = 0
	for i in range(1, n):
		if s[i] == s[0]:
			maximum_possible = i
			break
	else:
		maximum_possible = n
	ans = 1
	if len(indices) == 1:
		ans = len(s)
	else:
		done = False
		while ans < maximum_possible and (not done):
			for i in indices:
				if i + ans >= n or s[i + ans] != s[ans]:
					done = True
					break
			else:
				ans += 1
	print(s[:ans])


for _ in range(int(input())):
	n = int(input())
	txt = input().strip()
	(i, ans, start) = (1, n, 1)
	while i < n:
		if txt[i] == txt[0]:
			ans = min(ans, start)
			start = 1
			i += 1
		else:
			if txt[start] == txt[i]:
				start += 1
			else:
				ans = min(ans, start)
			i += 1
	ans = min(ans, start)
	print(txt[:ans])


t = int(input())
for i in range(0, t):
	n = int(input())
	s = input()
	ch = s[0]
	lis = []
	for j in range(0, n):
		if s[j] == ch:
			lis.append(j)
	l = len(lis)
	if l == 1:
		print(s)
	else:
		ht = 0
		for j in range(1, n):
			for k in range(0, l):
				if lis[k] + j > n - 1 or s[lis[k] + j] != s[j]:
					ht = 1
					break
			if ht == 1:
				break
		print(s[:j])


def res():
	for _ in range(int(input())):
		n = int(input())
		s = input().rstrip()
		c = s.count(s[0])
		if c == 1:
			print(s)
		else:
			i = 1 + s[1:].index(s[0])
			for j in range(len(s[:i]), 0, -1):
				if s.count(s[:j]) == c:
					print(s[:j])
					break
res()


t = int(input())
for _ in range(t):
	n = int(input())
	st = input()
	main = [0]
	maxi = 1
	maxi_se = st[0]
	prev = st[0]
	for i in range(1, n):
		if st[i] == st[0]:
			maxi += 1
			main.append(i)
	for i in range(1, n):
		prev += st[i]
		new_main = []
		count = 0
		for j in range(len(main)):
			if main[j] + 1 < n and st[main[j] + 1] == st[i]:
				count += 1
				new_main.append(main[j] + 1)
		if maxi < count:
			maxi = count
			maxi_se = prev
		elif maxi == count:
			maxi = count
			maxi_se = prev
		else:
			break
		if len(new_main) == 0:
			break
		else:
			main = new_main[:]
	print(maxi_se)


for _ in range(int(input())):
	length = int(input())
	s = input()
	c = 0
	pos = []
	for (ii, i) in enumerate(s):
		if i == s[0]:
			c += 1
			pos.append(ii)
	if c == 1:
		print(s)
		continue
	flag = 0
	prev_c = 0
	while flag == 0:
		prev_c += 1
		for p in pos:
			if length < p + prev_c:
				flag = 1
				break
			if s[0:prev_c] != s[p:p + prev_c]:
				flag = 1
				break
	print(s[0:prev_c - 1])


for _ in range(int(input().strip())):
	n = int(input().strip())
	string = input().strip()
	if string.count(string[0]) == 1:
		print(string)
	elif string.count(string[0]) == len(string):
		print(string[0])
	else:
		for i in range(1, len(string)):
			if string[0] == string[i]:
				sub = string[:i]
				break
		max_count = string.count(string[0])
		sc = string.count(sub)
		if sc >= max_count:
			print(sub)
		else:
			for i in range(1, len(sub)):
				if string.count(sub[:-i]) >= max_count:
					print(sub[:-i])
					break


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	max_length = n
	for j in range(1, n):
		i = 0
		if s[i] == s[j]:
			k = j + 1
			lim = min(j + max_length, n)
			while k < lim:
				i += 1
				if s[i] != s[k]:
					break
				k += 1
			max_length = k - j
	print(s[:max_length])


for _ in range(int(input())):
	n = int(input())
	s = str(input())
	x = s.count(s[0])
	if x == 1:
		print(s)
	else:
		(l, r) = (0, n // x + 1)
		mid = (l + r) // 2
		while l != r:
			mid = (l + r) // 2
			if s.count(s[:mid]) < x:
				r = mid
			else:
				l = mid
			if l == r - 1:
				if s.count(s[:l]) > s.count(s[:r]):
					mid = l
				else:
					mid = r
				break
		print(s[:mid])


def Tee():
	N = int(input())
	arr = input()
	arr_copy = arr[1:]
	min_possible = arr.count(arr[0])
	if min_possible == 1:
		return arr
	elif min_possible == N:
		return arr[0]
	index = 0
	index_list = [0]
	prev_index = index
	index = arr_copy.find(arr[0])
	while index >= 0:
		index_list.append(prev_index + index + 1)
		prev_index = prev_index + index + 1
		arr_copy = arr_copy[index + 1:]
		index = arr_copy.find(arr[0])
	length = len(index_list)
	add = 1
	while True:
		for i in range(1, length):
			if index_list[i] + add >= N or arr[add] != arr[index_list[i] + add]:
				return arr[:add]
		add += 1
for i in range(int(input())):
	print(Tee())


t = int(input())
for x in range(t):
	n = int(input())
	s = input()
	q = s.count(s[0])
	a = len(s) // q
	for i in range(a):
		if s.count(s[:a - i]) == q:
			print(s[:a - i])
			break
		else:
			continue


n = int(input())
t = 0
while t < n:
	N = int(input())
	S = input()
	maxoc = S.count(S[0])
	x = N // maxoc
	for i in range(0, x):
		pref = S[:x - i]
		if S.count(pref) == maxoc:
			print(pref)
			break
	t = t + 1


na = int(input())
for i in range(0, na):
	num1 = int(input())
	st = input()
	occ = st.count(st[0])
	a = num1 // occ
	for i in range(a):
		if st.count(st[:a - i]) == occ:
			print(st[:a - i])
			break


for t in range(int(input())):
	n = int(input())
	a = input()
	s = list(a)
	count = 0
	indi = n + 1
	r = s[0]
	result = [1 for i in range(0, n)]
	for i in range(1, n):
		if s[i] == r:
			result[0] += 1
			count = 1
			indi = i
		elif s[i] == s[count] and count < indi:
			result[count] += 1
			count += 1
		else:
			count = 0
	b = []
	for i in range(n):
		b.append([result[i], i + 1])
	b.sort(reverse=True)
	print(a[:b[0][1]])


T = int(input())
while T > 0:
	T -= 1
	N = int(input())
	string = input()
	prefix = []
	for i in range(len(string)):
		prefix.append(1)
	temp = False
	first_letter = string[0]
	var = 'A'
	k = 0
	for i in range(1, len(string)):
		if temp:
			var += string[i]
		if string[i] == first_letter:
			var = string[i]
			k = 0
		if var == string[:k + 1]:
			prefix[k] += 1
			temp = True
			k += 1
		else:
			temp = False
			k = 0
	max = -1
	for i in range(len(prefix)):
		if max <= prefix[i]:
			max = prefix[i]
			index = i
	if max != 1:
		print(string[:index + 1])
	else:
		print(string)


for _ in range(int(input())):
	n = int(input())
	s = input()
	idx = []
	ts = ''
	for i in range(n):
		if s[i] == s[0]:
			idx.append(i)
	idxl = len(idx)
	ans = 0
	for i in range(1, n):
		j = 0
		while j < idxl:
			if idx[j] + i >= n or s[idx[j] + i] != s[i]:
				ans = i
				break
			j += 1
		if ans:
			break
	if ans:
		print(s[0:ans])
	else:
		print(s)


for __ in range(int(input())):
	n = int(input())
	s = input()
	l = set(s.split(s[0]))
	m = 0
	a = s
	for i in l:
		k = s.count(s[0] + i)
		if k >= m:
			m = k
			a = s[0] + i
	print(a)


for _ in range(int(input())):
	m = n = int(input())
	s = input()
	for i in range(n - 1, 0, -1):
		if s[i] == s[0]:
			m = min(m, n - i)
			m = next((j for j in range(m) if s[i + j] != s[j]), m)
	print(s[:m])


t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	q = s.count(s[0])
	a = len(s) // q
	for j in range(a):
		if s.count(s[:a - j]) == q:
			print(s[:a - j])
			break


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	pos = []
	for i in range(n):
		if s[i] == s[0]:
			pos.append(i)
	length = 0
	done = False
	while length < n:
		for p in pos:
			if p + length >= n or s[p + length] != s[length]:
				done = True
				break
		if done:
			break
		length += 1
	print(s[:length])


for t in range(int(input())):
	n = int(input())
	y = input()
	a = list(y)
	h = []
	d = []
	j = 1
	for i in range(n):
		if a[i] == a[0]:
			d.append(i)
	count = a.count(a[0])
	if count == 1:
		print(''.join(a))
	elif a[-1] == a[0]:
		print(a[0])
	else:
		for i in range(d[1] + 1):
			d = [x + 1 for x in d]
			if d[-1] == n:
				break
			g = [a[x] for x in d]
			if g.count(g[0]) == count:
				j = j + 1
			else:
				break
		print(''.join(a[0:j]))


T = int(input())
for test_case in range(T):
	N = int(input())
	S = input()
	index = list()
	for i in range(N):
		if S[i] == S[0]:
			index.append(i)
	(ans, flag, count) = (S[0], True, 1)
	while flag and index[-1] + count < N:
		if all([S[i + count] == S[count] for i in index]):
			ans = S[:count + 1]
		else:
			flag = False
		count += 1
	print(ans)


T = int(input())
for _ in range(T):
	N = int(input())
	S = input()
	l = [0]
	for i in range(1, N):
		if S[i] == S[0]:
			l.append(i)
	result = S[0]
	if len(l) == 1:
		print(S)
	else:
		for i in range(1, l[1]):
			ch = S[i]
			flag = 1
			for j in l:
				if j + i < N:
					if S[j + i] != ch:
						flag = -1
						break
				else:
					flag = -1
					break
			if flag == -1:
				break
			else:
				result = S[0:i + 1]
		print(result)


t = int(input())
for s in range(t):
	n = int(input())
	st = input()
	d = st.count(st[0])
	a = len(st) // d
	for i in range(a):
		if st.count(st[:a - i]) == d:
			print(st[:a - i])
			break
		else:
			continue


t = int(input())
while t:
	t -= 1
	n = int(input())
	s = input()
	l = []
	i = 1
	l.append(0)
	while i < n:
		try:
			l.append(l[i - 1] + 1 + s[l[i - 1] + 1:].index(s[0]))
		except:
			break
		i += 1
	k = ''
	i = 1
	if len(l) == 1:
		print(s)
	else:
		k += s[i - 1]
		while i < n:
			for j in range(len(l)):
				try:
					if s[l[j] + 1] != s[i]:
						i = n
						break
					l[j] += 1
				except:
					i = n
					break
			if i != n:
				k += s[i]
			i += 1
		print(k)


for t in range(int(input())):
	n = int(input())
	text = input()
	check = [i for i in range(1, n) if text[i] == text[0]]
	l = len(check)
	if not l:
		print(text)
		continue
	pat = text[0]
	next_index = 1
	flag = 0
	for i in range(n - check[-1] - 1):
		for j in check:
			if text[j + next_index] != text[next_index]:
				flag = 1
				break
		if flag:
			break
		pat = pat + text[next_index]
		next_index += 1
	print(pat)


T = int(input())
for _ in range(T):
	N = int(input())
	que = input()
	n = len(que)
	start = [i for i in range(1, N) if que[0] == que[i]]
	if start == []:
		print(que)
	else:
		ans = ''
		for i in range(0, start[0]):
			flag = 0
			for j in start:
				if j + i >= N or que[j + i] != que[i]:
					flag = 1
					break
			if flag:
				break
			ans = ans + que[i]
		print(ans)


def check(lst):
	for i in range(len(lst)):
		if i > 0:
			if lst[i] != lst[i - 1]:
				return False
	return True
for i in range(int(input())):
	n = int(input())
	stn = input()
	y = len(stn)
	l = []
	for i in range(len(stn)):
		if stn[i] == stn[0]:
			l.append(i)
	x = []
	while len(x) != len(l):
		x.append(1)
	ans = 1
	f = l[:]
	while True:
		f = list(map(lambda z, y: z + y, f, x))
		t = []
		p = False
		for i in f:
			if i >= len(stn):
				p = True
				break
			else:
				t.append(stn[i])
		if p:
			break
		if check(t):
			ans += 1
		else:
			break
	if len(f) == 1:
		print(stn)
	else:
		print(stn[:ans])


t = int(input())
for i in range(t):
	n = int(input())
	a = input()
	l = list(a)
	li = []
	k = 0
	for j in range(n):
		if l[j] == l[0]:
			li.append(j)
			k = k + 1
	m = 1
	flag = 0
	while 1:
		try:
			for j in range(k):
				if l[li[j] + m] != l[li[0] + m]:
					ans = m
					flag = 1
					break
		except:
			ans = m
			flag = 1
		if flag == 1:
			break
		else:
			m = m + 1
	print(a[:m])


t = int(input())
for i in range(t):
	n = int(input())
	string = input()
	first = string.count(string[0])
	total = len(string)
	maxLength = total // first
	for j in range(maxLength):
		if string.count(string[:maxLength - j]) == first:
			print(string[:maxLength - j])
			break


t = int(input())
for _ in range(t):
	n = int(input())
	s = str(input())
	k = s.count(s[0])
	if k == 1:
		print(s)
	else:
		a = n // k
		for i in range(a):
			if s.count(s[:a - i]) == k:
				print(s[:a - i])
				break
			else:
				continue


t = int(input())
for i in range(t):
	n = int(input())
	s = input().strip()
	x = s[0]
	ind = []
	for j in range(n):
		if s[j] == x:
			ind.append(j)
	if len(ind) == 1:
		print(s)
		continue
	f = 1
	travel = 0
	op = ''
	while f:
		x = s[travel]
		if ind[len(ind) - 1] + travel >= n:
			f = 0
			break
		for index in ind:
			if s[index + travel] == x:
				continue
			else:
				f = 0
				break
		if f:
			op = op + x
			travel = travel + 1
	print(op)


t = int(input())
for _ in range(t):
	pfx = []
	n = int(input())
	s = input()
	for i in range(1, n):
		if s[i] == s[0]:
			pfx.append(i)
	if len(pfx) == 0:
		print(s)
	else:
		mc = 0
		flag = 1
		lim = pfx[0]
		for i in range(1, lim + 1):
			for j in pfx:
				if i + j < n:
					if s[i] != s[i + j]:
						flag = 0
						break
				else:
					flag = 0
					break
			if flag == 0:
				mc = i
				break
		print(s[:mc])


for _ in range(int(input())):
	n = int(input())
	st = input()
	t = st[0]
	if st.count(t) == 1:
		print(st)
		continue
	l = []
	for (i, j) in enumerate(st):
		if j == t:
			l.append(i)
	c = 1
	l1 = len(l)
	while 1:
		co = 0
		if l[0] + c != n:
			t = st[l[0] + c]
		else:
			break
		for i in l:
			if i + c == n:
				break
			if st[i + c] == t:
				co += 1
			else:
				break
		if co != l1:
			break
		c = c + 1
	print(st[:c])


for _ in range(int(input())):
	n = int(input())
	arr = list(input())
	list2 = []
	(i, j, max_len, leng) = (0, 1, 1, 1)
	while i <= n - 1:
		if arr[i] == arr[0]:
			j = 1
			i += 1
			leng = 1
			while i <= n - 1 and j <= n - 1 and (arr[i] == arr[j]) and (arr[i] != arr[0]):
				leng += 1
				i += 1
				j += 1
			list2.append(leng)
		else:
			i += 1
	print(''.join(arr[:min(list2)]))


T = int(input())
for i in range(0, T):
	N = int(input())
	s = input()
	L = []
	for j in range(0, len(s)):
		if s[j] == s[0]:
			L.append(j)
	if len(L) == 1:
		print(s)
	else:
		c = 1
		flag = 0
		while flag == 0:
			temp = 0
			for j in range(0, len(L)):
				if L[j] + c < len(s):
					if s[L[j] + c] == s[c]:
						temp = temp + 1
				else:
					flag = 1
					break
			if temp == len(L):
				c = c + 1
			else:
				flag = 1
		print(s[:c])


T = int(input())
for testcase in range(T):
	N = int(input())
	S = str(input())
	maxlen = N
	if N == 1:
		print(S)
		continue
	fst = S[0]
	idxlist = []
	for i in range(1, N):
		if S[i] == fst:
			idxlist.append(i)
	if len(idxlist) == 0:
		print(S)
		continue
	ichar = idxlist[0]
	for i in range(len(idxlist)):
		ichar = idxlist[i]
		j = 0
		while ichar < N:
			if S[ichar] == S[j]:
				ichar += 1
			else:
				break
			j += 1
		maxlen = min(maxlen, j)
	print(S[0:maxlen])


t = int(input())
for i in range(t):
	n = int(input())
	string = input()
	o = string.count(string[0])
	l = len(string)
	maxIndexItCanBeTill = l // o
	for x in range(maxIndexItCanBeTill):
		if string.count(string[:maxIndexItCanBeTill - x]) == o:
			print(string[:maxIndexItCanBeTill - x])
			break
		else:
			continue


for i in range(int(input())):
	n = int(input())
	s = input()
	l = []
	c = 0
	for i in range(1, n):
		if s[i] == s[0]:
			l.append(i)
	if len(l) == n - 1:
		p = s
	else:
		for i in range(1, n + 1):
			count = 0
			for j in range(len(l)):
				if l[j] >= i and l[j] + i - 1 < n:
					if s[l[j] + i - 1] == s[i - 1]:
						count += 1
					else:
						l[j] = -1
			if count >= c:
				c = count
				p = s[:i]
			else:
				break
	print(p)


t = int(input())
while t > 0:
	n = int(input())
	l = input()
	l = l + '00'
	b = l[0]
	g = []
	for i in range(1, n):
		if l[i] == b:
			g.append(i)
	flag = 1
	if g == []:
		print(l[0:n])
	else:
		for i in range(1, g[0] + 1):
			if flag == 1:
				for j in g:
					if l[i] != l[j + i]:
						print(l[0:i])
						flag = 0
						break
	t = t - 1


test = int(input())
for x in range(test):
	n = int(input())
	hint = input()
	count = hint.count(hint[0])
	lim = n // count
	for i in range(lim):
		temp = hint[0:lim - i]
		if hint.count(temp) == count:
			print(hint[0:lim - i])
			break
		else:
			continue


def m():
	t = int(input())
	while t > 0:
		n = int(input())
		s = input()
		length = len(s)
		k = ''
		l = []
		l1 = []
		c = s.count(s[0])
		pcs = int(length / c)
		if c == 1:
			print(s)
		else:
			for i in range(pcs):
				if s.count(s[:pcs - i]) == c:
					print(s[:pcs - i])
					break
		t -= 1
m()


for _ in range(int(input())):
	n = int(input())
	a = list(input())
	b = [0] * n
	j = 0
	while j < n:
		b[j] += 1
		i = j
		k = 0
		while j < n and k < i and (a[j] == a[k]):
			b[k] += 1
			k += 1
			j += 1
		j += 1
	c = max(b)
	j = n - 1
	while b[j] != c:
		j -= 1
	print(''.join(a[:j + 1]))


t = int(input())
while t > 0:
	n = int(input())
	strr = input()
	f_count = strr.count(strr[0])
	piece = len(strr) // f_count
	for i in range(piece):
		if strr.count(strr[:piece - i]) == f_count:
			print(strr[:piece - i])
			break
		else:
			continue
	t -= 1


t = int(input())
for t_i in range(t):
	n = int(input())
	string = input()
	ncc = n
	for i in range(1, n):
		j = i
		k = 0
		nc = ncc
		flag = False
		while j < n and k < nc:
			if string[k] == string[j]:
				if flag:
					ncc += 1
				else:
					ncc = 1
					flag = True
				k += 1
				j += 1
			else:
				break
	print(string[:ncc])


for _ in range(int(input())):
	n = int(input())
	s = input()
	c = 0
	L = []
	for i in range(n):
		if s[i] == s[0]:
			c += 1
			L.append(i)
	p = n // c
	i = 1
	f = 0
	while i <= p:
		for j in L:
			if j + i >= n:
				f = 1
				break
			if s[i] != s[j + i]:
				f = 1
				break
		if f:
			break
		i += 1
	print(s[:i])


test = int(input())
for _ in range(test):
	n = int(input())
	spass = input()
	pos = []
	for i in range(n):
		if spass[i] == spass[0]:
			pos.append(i)
	ans = 1
	while 1:
		ok = True
		for it in pos:
			if it + ans >= n:
				ok = False
				break
			if spass[it + ans] != spass[ans]:
				ok = False
				break
		if not ok:
			break
		ans += 1
	print(spass[:ans])


t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	x = set(s.split(s[0]))
	m = 0
	for i in x:
		k = s.count(s[0] + i)
		if k >= m:
			m = k
			a = s[0] + i
	print(a)


for _ in range(int(input())):
	n = int(input())
	s = input()
	pos = []
	for i in range(1, len(s)):
		if s[i] == s[0]:
			pos.append(i)
	if len(pos) == 0:
		print(s)
	else:
		i = 1
		f = 1
		while i < pos[0]:
			for j in pos:
				if i + j >= n:
					f = 0
					break
				if i + j < n and s[i] != s[j + i]:
					f = 0
					break
			if f == 0:
				break
			i += 1
		print(s[:i])