Flamel is making the Elixir of Life but he is missing a secret ingredient, a set of contiguous plants (substring) from the Garden of Eden.
The garden consists of various plants represented by string S, where each letter represents a different plant.  But the prophecy has predicted that the correct set of plants required to make the potion will appear in the same contiguous pattern (substring) at the beginning of the forest (prefix), the end of the forest (suffix), and will also be the most frequent sequence present in the entire forest.
Identify the substring of plants required to make the elixir and find out the number of times it appears in the forest. 
Example 1:
Input: S = "ababaaaab"
Output: 3
Explanation: Substring "ab" is a prefix, 
It is also a suffix and appears 3 times.
Example 2:
Input: S = "aaaa"
Output: 4
Explanation: Substring "aaaa" occurs 1 time, 
Substring "aaa" occurs 2 times, substring 
"aa" occurs 3 times, substring "a" occurs 
4 times. All of them are proper prefixes 
and suffixes. But, "a" has the maximum 
frequency.
Example 3:
Input: S = "abcdef"
Output: 1
Your Task: 
You don't need to read input or print anything. Complete the function maxFrequency() which takes string S as input parameter and returns the frequency of the most frequent substring of S which is also a prefix and suffix of the original string.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints: 
1 ≤ |S| ≤ 10^{5}

Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)

Starter code:
#User function Template for python3

class Solution:
    def maxFrequency(self, S):
        # code here

Solutions:
class Solution:

	def z_function(self, s):
		n = len(s)
		z = [0] * n
		z[0] = n
		(l, r) = (0, 0)
		for i in range(1, n):
			if i < r:
				z[i] = min(r - i, z[i - l])
			while i + z[i] < n and s[z[i]] == s[i + z[i]]:
				z[i] += 1
			if i + z[i] > r:
				r = i + z[i]
				l = i
		return z

	def maxFrequency(self, S):
		z = self.z_function(S)
		ans = 0
		n = len(S)
		for i in range(n - 1, -1, -1):
			if z[i] == n - i:
				suffix = S[-z[i]:]
				start = 0
				while True:
					pos = S.find(suffix, start)
					if pos == -1:
						return ans
					ans += 1
					start = pos + len(suffix)
		return ans


class Solution:

	def maxFrequency(self, S):
		a = S[0]
		for i in range(len(S) - 1, -1, -1):
			if S[i:] == S[0:len(S) - i]:
				a = S[i:]
				break
		return S.count(a)


class Solution:

	def maxFrequency(self, S):
		st = ''
		n = len(S)
		for i in S:
			st += i
			if st == S[n - len(st):]:
				break
		cnt = 0
		for i in range(n - len(st) + 1):
			if S[i:i + len(st)] == st:
				cnt += 1
		return cnt


class Solution:

	def find_shortest_presuffix(self, S):
		for i in range(len(S)):
			if S[i] == S[-1] and S[:i + 1] == S[-(i + 1):]:
				return S[:i + 1]

	def maxFrequency(self, S):
		if not S:
			return 0
		shortest_presuffix = self.find_shortest_presuffix(S)
		return S.count(shortest_presuffix)


class Solution:

	def maxFrequency(self, str):
		flag = False
		L = len(str)
		if str[0] == str[L - 1]:
			freq = str.count(str[0])
			return freq
		for i in range(1, L // 2):
			if str[0] == str[L - 1 - i]:
				for j in range(i + 1):
					if str[j] == str[L - i - 1 + j]:
						flag = True
						continue
					else:
						flag = False
						break
				if flag == True:
					freq = str.count(str[0:i + 1])
					return freq
		return 1


class Solution:

	def maxFrequency(self, S):
		n = len(S)
		count = 1
		plant = ''
		for i in range(n):
			if S[:i + 1] == S[-i - 1:]:
				plant = S[:i + 1]
				break
		for i in range(len(plant), n):
			if plant == S[i:i + len(plant)]:
				count += 1
		return count


class Solution:

	def maxFrequency(self, s):
		for i in range(len(s)):
			if s.endswith(s[:i + 1]):
				return s.count(s[:i + 1])
		return 1


class Solution:

	def maxFrequency(self, s):
		t = ''
		for i in s:
			t += i
			n = len(t)
			if t == s[len(s) - n:]:
				temp = t
				break
		n = len(t)
		ans = 1
		for i in range(n, len(s)):
			if temp == s[i:i + n]:
				ans += 1
		return ans


class Solution:

	def maxFrequency(self, S):
		for i in range(1, len(S)):
			if S[:i] == S[len(S) - i:]:
				return S.count(S[:i])
		return 1


class Solution:

	def maxFrequency(self, S):
		a = S[0]
		for i in range(len(S) - 1, -1, -1):
			if S[i:] == S[0:len(S) - i]:
				a = S[i:]
				break
		return S.count(a)
from collections import defaultdict
if __name__ == '__main__':
	T = int(input())
	for _ in range(T):
		Str = input()
		obj = Solution()
		print(obj.maxFrequency(Str))


class Solution:

	def maxFrequency(self, S):
		ch = ''
		for i in range(len(S) // 2):
			if S[:i + 1] == S[len(S) - i - 1:]:
				ch = S[:i + 1]
				break
		if len(ch) == 0:
			return 1
		else:
			res = S.count(ch)
			return res


class Solution:

	def maxFrequency(self, S):
		i = 0
		j = len(S) - 1
		while i < j:
			if S[:i + 1] == S[j:]:
				return S.count(S[i])
			else:
				i += 1
				j -= 1
				if S[:i + 1] == S[j:]:
					return S.count(S[j:])
		return 1


class Solution:

	def maxFrequency(self, S):
		if len(S) == S.count('a'):
			return len(S)
		if len(S) == 1:
			return 1
		st = []
		for i in range(len(S) // 2):
			if S[i] == S[-1]:
				if S[:i + 1] == S[len(S) - i - 1:]:
					st.append(S[:i + 1])
		maxi = []
		for i in st:
			maxi.append(S.count(i))
		if not maxi:
			return 1
		else:
			return max(maxi)


class Solution:

	def maxFrequency(self, S):
		st = ''
		n = len(S)
		for i in S:
			st += i
			if st == S[n - len(st):]:
				break
		cnt = S.count(st)
		return cnt


class Solution:

	def maxFrequency(self, S):
		if S.count(S[0]) == len(S):
			return len(S)
		i = 0
		j = len(S) - 1
		x1 = ''
		x2 = ''
		z = ''
		while i < j:
			x1 = x1 + S[i]
			x2 = S[j] + x2
			if x1 == x2:
				z = x1
				break
			i = i + 1
			j = j - 1
		if z:
			return S.count(z)
		return 1


class Solution:

	def maxFrequency(self, S):
		a = ''
		l = len(S)
		for i in S:
			a = a + i
			if a == S[l - len(a):]:
				return S.count(a)
		return 1


class Solution:

	def maxFrequency(self, S):
		index = 1
		l = len(S)
		arr_dict = dict()
		subStr = []
		if S.count(S[0]) == len(S):
			return len(S)
		for index in range(1, len(S)):
			if S[0:index] == S[-index:l]:
				subStr.append(S[0:index])
		if len(subStr) == 0:
			return 1
		hightCnt = 0
		for items in subStr:
			hightCnt = max(hightCnt, S.count(items))
		return hightCnt


class Solution:

	def maxFrequency(self, s):
		(z, l, r) = ([0] * len(s), -1, -1)
		for i in range(1, len(s)):
			z[i] = min(r - i, z[i - l]) if i < r else 0
			while i + z[i] < len(z) and s[i + z[i]] == s[z[i]]:
				z[i] += 1
			if i + z[i] > r:
				(l, r) = (i, i + z[i])
		k = len(s)
		for i in range(len(s) - 1, -1, -1):
			if z[i] == len(s) - i:
				k = z[i]
				break
		ans = 1
		for x in z:
			if x >= k:
				ans += 1
		return ans


class Solution:

	def maxFrequency(self, s):
		n = len(s)
		s1 = ''
		for i in s:
			if i not in s1:
				s1 += i
			if s == s1:
				return 1
			temp = ''
			for i in range(1, n):
				if s[:i] == s[n - i:n]:
					temp = s[:i]
					break
				else:
					temp = s
			c = s.count(temp)
			return c


class Solution:

	def maxFrequency(self, s):
		if len(s) == 1:
			return 1
		st = ''
		sub = ''
		count = 0
		left = 0
		ans = s
		s = list(s)
		right = len(s) - 1
		while left < right:
			st += s[left]
			sub = s[right] + sub
			if st == sub:
				break
			left += 1
			right -= 1
		count = ans.count(sub)
		return count


class Solution:

	def maxFrequency(self, S):
		l = list(S)
		i = 1
		j = len(l) - 1
		a = ''
		while i <= j:
			f = l[0:i]
			s = l[j:]
			if f == s:
				a = ''.join(f)
				break
			i += 1
			j -= 1
		if len(a) == 0:
			return 1
		return S.count(a)