Shaka and his brother have created a boring game which is played like this:  

They take a word composed of lowercase English letters and try to get the maximum possible score by building exactly 2 palindromic subsequences. The score obtained is the product of the length of these 2 subsequences.

Let's say $\mbox{A}$ and $\mbox{B}$ are two subsequences from the initial string. If $A_i$ & $A_j$ are the smallest and the largest positions (from the initial word) respectively in $\mbox{A}$ ; and $B_i$ & $B_j$ are the smallest and the largest positions (from the initial word) respectively in $\mbox{B}$, then the following statements hold true: 

$A_i\leq A_j$, 

$B_i\leq B_j$, & 

$A_j<B_i$. 

i.e., the positions of the subsequences should not cross over each other. 

Hence the score obtained is the product of lengths of subsequences $\mbox{A}$ & $\mbox{B}$. Such subsequences can be numerous for a larger initial word, and hence it becomes harder to find out the maximum possible score. Can you help Shaka and his brother find this out?

Input Format

Input contains a word $\mbox{S}$ composed of lowercase English letters in a single line.  

Constraints

$1<|S|\leq3000$ 

each character will be a lower case english alphabet.  

Output Format

Output the maximum score the boys can get from $\mbox{S}$.

Sample Input
eeegeeksforskeeggeeks

Sample Output
50

Explanation

A possible optimal solution is eee-g-ee-ksfor-skeeggeeks being eeeee the one subsequence and skeeggeeks the other one. We can also select eegee in place of eeeee, as both have the same length.

Source: hackerrank | Difficulty: MEDIUM
Tags: Dynamic programming


Solutions:
def findMaxSubsequence(seq):
	length = len(seq)
	seqLength = [[0 for i in range(length)] for j in range(length)]
	for i in range(length):
		seqLength[i][i] = 1
	for cols in range(2, length + 1):
		for i in range(0, length - cols + 1):
			j = i + cols - 1
			if seq[i] == seq[j]:
				if cols == 2:
					seqLength[i][j] = 2
				else:
					seqLength[i][j] = seqLength[i + 1][j - 1] + 2
			else:
				seqLength[i][j] = max(seqLength[i + 1][j], seqLength[i][j - 1])
	return seqLength
string = list(input())
seqLength = findMaxSubsequence(string)
maxScore = 0
for i in range(0, len(string) - 1):
	left = seqLength[0][i]
	right = seqLength[i + 1][-1]
	score = left * right
	if score > maxScore:
		maxScore = score
print(maxScore)


s = input()
p = [[0] * len(s) for _ in range(len(s))]
for i in range(len(s)):
	p[i][i] = 1
for k in range(2, len(s) + 1):
	for i in range(len(s) - k + 1):
		j = i + k - 1
		if s[i] == s[j]:
			p[i][j] = 2 + (0 if k == 2 else p[i + 1][j - 1])
		else:
			p[i][j] = max(p[i][j - 1], p[i + 1][j])
print(max((p[0][i] * p[i + 1][-1] for i in range(len(s) - 1))))


import sys
sys.setrecursionlimit(3500)
s = input()
d = [[-1] * (len(s) - i) for i in range(0, len(s))]

def largestPalindrome(start, end):
	if start > end:
		return 0
	if start == end:
		return 1
	if d[start][end - start] != -1:
		return d[start][end - start]
	if s[start] == s[end]:
		v = 2 + largestPalindrome(start + 1, end - 1)
	else:
		v = max(largestPalindrome(start + 1, end), largestPalindrome(start, end - 1))
	d[start][end - start] = v
	return v
m = 0
for i in range(1, len(s) - 1):
	m = max(m, largestPalindrome(0, i) * largestPalindrome(i + 1, len(s) - 1))
print(m)


def lps(s):
	result = [[0 for _ in range(len(s) + 1)] for _ in range(len(s) + 1)]
	for i in range(1, len(s) + 1):
		result[1][i] = 1
	result[1][-1] = 0
	for i in range(2, len(s)):
		for j in range(0, len(s) - i + 1):
			if s[j] == s[j + i - 1]:
				result[i][j + 1] = 2 + result[i - 2][j + 2]
			else:
				result[i][j + 1] = max(result[i - 1][j + 1], result[i - 1][j + 2])
	return result

def max_product(s):
	table = lps(s)
	max_pr = 0
	for i in range(1, len(s) - 1):
		max_pr = max(max_pr, table[i][1] * table[len(s) - i][i + 1])
	return max_pr
s = input()
print(max_product(s))


def main():
	import sys
	sys.setrecursionlimit(9000000)
	S = input()
	l = len(S)
	dp = [[-1] * l for i in range(l)]
	maximum = -1

	def sub(i, j):
		if dp[i][j] != -1:
			return dp[i][j]
		elif i == j:
			dp[i][j] = 1
		elif i > j:
			dp[i][j] = 0
		elif S[i] == S[j]:
			dp[i][j] = 2 + sub(i + 1, j - 1)
		else:
			dp[i][j] = max(sub(i, j - 1), sub(i + 1, j))
		return dp[i][j]
	sub(0, l - 1)
	for i in range(l - 1):
		if dp[0][i] == -1:
			dp[0][i] = sub(0, i)
		if dp[i + 1][l - 1] == -1:
			dp[i + 1][l - 1] = sub(i + 1, l - 1)
		maximum = max(maximum, dp[0][i] * dp[i + 1][l - 1])
	print(maximum)
main()


word = str(input())
lenght = len(word)
dp = [[float('-infinity')] * lenght for i in range(lenght)]

def palindromic():
	for k in range(lenght):
		for i in range(lenght - k):
			j = i + k
			if i == j:
				dp[i][j] = 1
			elif word[i] == word[j]:
				if k == 1:
					dp[i][j] = 2
				else:
					dp[i][j] = 2 + dp[i + 1][j - 1]
			else:
				dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
	print(max((dp[0][i] * dp[i + 1][-1] for i in range(len(word) - 1))))
palindromic()


def findMaxSubsequence(seq):
	length = len(seq)
	seqLength = [[0 for i in range(length)] for j in range(length)]
	for i in range(length):
		seqLength[i][i] = 1
	for cols in range(2, length + 1):
		for i in range(0, length - cols + 1):
			j = i + cols - 1
			if seq[i] == seq[j]:
				if cols == 2:
					seqLength[i][j] = 2
				else:
					seqLength[i][j] = seqLength[i + 1][j - 1] + 2
			else:
				seqLength[i][j] = max(seqLength[i + 1][j], seqLength[i][j - 1])
	return seqLength
string = list(input())
seqLength = findMaxSubsequence(string)
maxScore = 0
for i in range(0, len(string) - 1):
	left = seqLength[0][i]
	right = seqLength[i + 1][-1]
	score = left * right
	if score > maxScore:
		maxScore = score
print(maxScore)


S = input().rstrip()
N = len(S)
dp = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N):
	dp[i][i] = 1
for sublen in range(2, N + 1):
	for i in range(0, N - sublen + 1):
		j = i + sublen - 1
		if S[i] == S[j]:
			dp[i][j] = dp[i + 1][j - 1] + 2
		else:
			dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
score = 0
for i in range(N - 1):
	tmp = dp[0][i] * dp[i + 1][N - 1]
	score = max(tmp, score)
print(score)


S = input()
n = len(S)
lps = [[0 for _ in range(n)] for _ in range(n)]
for i in reversed(range(n)):
	lps[i][i] = 1
	for j in range(i + 1, n):
		if S[i] == S[j]:
			lps[i][j] = 2 + lps[i + 1][j - 1]
		else:
			lps[i][j] = max(lps[i + 1][j], lps[i][j - 1])
m = 0
for i in range(n - 1):
	m = max(m, lps[0][i] * lps[i + 1][n - 1])
print(m)


import sys
__author__ = 'nutic'

def max_substr_palindrom_table(str):
	table = [[0 for _ in str] for _ in str]
	for i in range(len(table) - 1, -1, -1):
		for j in range(i, len(table)):
			if i == j:
				table[i][j] = 1
			elif str[i] == str[j]:
				table[i][j] = table[i + 1][j - 1] + 2
			else:
				table[i][j] = max(table[i + 1][j], table[i][j - 1])
	return table

def max_score(str):
	table = max_substr_palindrom_table(str)

	def max_score_at(i):
		str1 = str[:i]
		str2 = str[i:]
		if len(str1) == 0:
			return 0
		if len(str2) == 0:
			return 0
		return table[0][i - 1] * table[i][len(str) - 1]
	return max((max_score_at(i) for (i, _) in enumerate(str) if len(str[:i])))
print(max_score(sys.stdin.read()))


def palindromes(s):
	n = len(s)
	P = [[0] * (n + 1) for _ in range(n + 1)]
	for d in range(n + 1):
		i = 0
		j = d
		while i <= n and j <= n:
			if j - i < 1:
				P[i][j] = 0
			elif j - i == 1:
				P[i][j] = 1
			elif s[i] == s[j - 1]:
				P[i][j] = 2 + P[i + 1][j - 1]
			else:
				P[i][j] = max(P[i + 1][j - 1], P[i][j - 1], P[i + 1][j])
			i += 1
			j += 1
	return P

def L(P_matrix):
	L = []
	max_seen = 0
	for j in range(len(P_matrix[0])):
		for i in range(len(P_matrix)):
			if P_matrix[i][j] > max_seen:
				max_seen = P_matrix[i][j]
		L.append(max_seen)
	return L

def R(P_matrix):
	R = [0] * len(P_matrix)
	max_seen = 0
	for i in reversed(range(len(P_matrix) - 1)):
		m = max(P_matrix[i])
		max_seen = max(max_seen, m)
		R[i] = max_seen
	return R
P = palindromes(input())
print(max((l * r for (l, r) in zip(L(P), R(P)))))


str = input()
slen = len(str)
dp = [[0 for x in range(slen)] for x in range(slen)]
for clen in range(1, slen + 1):
	for i in range(0, slen - clen + 1):
		if clen == 1:
			dp[i][i] = 1
		elif clen == 2:
			dp[i][i + 1] = 2 if str[i] == str[i + 1] else 1
		elif str[i] == str[i + clen - 1]:
			dp[i][i + clen - 1] = dp[i + 1][i + clen - 2] + 2
		else:
			dp[i][i + clen - 1] = max(dp[i + 1][i + clen - 2], dp[i + 1][i + clen - 1], dp[i][i + clen - 2])
ret = 1
for i in range(0, slen - 1):
	len1 = dp[0][i]
	len2 = dp[i + 1][slen - 1]
	ret = max(ret, len1 * len2)
print(ret)


A = input()
N = len(A)
L = []
for _ in range(N):
	L.append(N * [1])
for c in range(2, N + 1):
	for i in range(0, N - c + 1):
		j = i + c - 1
		if A[i] == A[j] and c == 2:
			L[i][j] = 2
		elif A[i] == A[j]:
			L[i][j] = L[i + 1][j - 1] + 2
		else:
			L[i][j] = max(L[i][j - 1], L[i + 1][j])
curMax = 0
for i in range(0, N - 1):
	j = i + 1
	v = L[0][i] * L[j][N - 1]
	curMax = max(curMax, v)
print(curMax)


def strplay(s):
	best = [[0, 1] for _ in s]
	for phase in range(1, len(s)):
		for i in range(len(s) - phase):
			besti = max(best[i][-1], best[i + 1][-1])
			if s[i] == s[i + phase]:
				besti = max(besti, 2 + best[i + 1][-2])
			best[i].append(besti)
	score = 0
	for i in range(len(s) - 1):
		score = max(score, best[0][i] * best[i][-1])
	return score
print(strplay(input().strip()))


def LPS(A):
	Arev = A[::-1]
	N = len(A)
	L = [[0 for i in range(N + 1)] for j in range(N + 1)]
	for i in range(1, N + 1):
		L[1][i] = 1
	for i in range(2, N):
		for j in range(0, N - i + 1):
			if A[j] == A[j + i - 1]:
				L[i][j + 1] = 2 + L[i - 2][j + 2]
			else:
				L[i][j + 1] = max(L[i - 1][j + 1], L[i - 1][j + 2])
	res = 0
	for i in range(1, N - 1):
		res = max(L[i][1] * L[N - i][i + 1], res)
	return res
print(LPS(input()))


def main():
	s = input()
	n = len(s)
	dp = [[0] * (n + 1) for i in range(n)]
	for i in range(0, n):
		dp[i][1] = 1
	for j in range(2, n + 1):
		for i in range(n - j + 1):
			if s[i] == s[i + j - 1]:
				dp[i][j] = dp[i + 1][j - 2] + 2
			else:
				dp[i][j] = max(dp[i][j - 1], dp[i + 1][j - 1])
	ans = 0
	for i in range(1, len(s) - 1):
		ans = max(ans, dp[0][i] * dp[i][len(s) - i])
	print(ans)
main()


iStr = input()
N = len(iStr)
DP = [[0] * N for _ in range(N)]
for i in range(N):
	DP[i][i] = 1
for sublen in range(2, N + 1):
	for i in range(N - sublen + 1):
		j = i + sublen - 1
		if iStr[i] == iStr[j] and sublen == 2:
			DP[i][j] = 2
		elif iStr[i] == iStr[j]:
			DP[i][j] = DP[i + 1][j - 1] + 2
		else:
			DP[i][j] = max(DP[i + 1][j], DP[i][j - 1])
maxProduct = 0
for i in range(N - 1):
	curProduct = DP[0][i] * DP[i + 1][N - 1]
	if curProduct > maxProduct:
		maxProduct = curProduct
print(maxProduct)


str = input()
slen = len(str)
dp = [[0 for x in range(slen)] for x in range(slen)]
for clen in range(1, slen + 1):
	for i in range(0, slen - clen + 1):
		if clen == 1:
			dp[i][i] = 1
		elif clen == 2:
			dp[i][i + 1] = 2 if str[i] == str[i + 1] else 1
		elif str[i] == str[i + clen - 1]:
			dp[i][i + clen - 1] = dp[i + 1][i + clen - 2] + 2
		else:
			dp[i][i + clen - 1] = max(dp[i + 1][i + clen - 2], dp[i + 1][i + clen - 1], dp[i][i + clen - 2])
ret = 1
for i in range(0, slen - 1):
	len1 = dp[0][i]
	len2 = dp[i + 1][slen - 1]
	ret = max(ret, len1 * len2)
print(ret)


def pdp(cs):
	l = len(cs)
	mem = [[0] * l for _ in range(l)]
	mem[0][0] = 1
	mem[l - 1][l - 1] = 1
	for i in reversed(range(l)):
		for j in range(i, l):
			if j == 0:
				continue
			if i == l - 1:
				continue
			if i == j:
				mem[i][j] = 1 + mem[i + 1][j - 1]
			elif cs[i] == cs[j]:
				mem[i][j] = 2 + mem[i + 1][j - 1]
			else:
				mem[i][j] = max(mem[i + 1][j], mem[i][j - 1])
	return mem

def pdp2(cs):
	mem = pdp(cs)
	return max((mem[0][j] * mem[j + 1][len(cs) - 1] for j in range(len(cs) - 1)))
print(pdp2(input()))


str = input()
slen = len(str)
dp = [[0 for x in range(slen)] for x in range(slen)]
for clen in range(1, slen + 1):
	for i in range(0, slen - clen + 1):
		if clen == 1:
			dp[i][i] = 1
		elif clen == 2:
			dp[i][i + 1] = 2 if str[i] == str[i + 1] else 1
		elif str[i] == str[i + clen - 1]:
			dp[i][i + clen - 1] = dp[i + 1][i + clen - 2] + 2
		else:
			dp[i][i + clen - 1] = max(dp[i + 1][i + clen - 2], dp[i + 1][i + clen - 1], dp[i][i + clen - 2])
ret = 1
for i in range(0, slen - 1):
	len1 = dp[0][i]
	len2 = dp[i + 1][slen - 1]
	ret = max(ret, len1 * len2)
print(ret)


def lps(s):
	n = len(s)
	dp = [[0] * n for _ in range(n)]
	for l in range(1, n + 1):
		for i in range(n - l + 1):
			j = i + l - 1
			if i == j:
				dp[i][j] = 1
			elif s[i] == s[j]:
				if l == 2:
					dp[i][j] = 2
				else:
					dp[i][j] = dp[i + 1][j - 1] + 2
			else:
				dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
	ret = 0
	for i in range(n - 1):
		ret = max(dp[0][i] * dp[i + 1][n - 1], ret)
	return ret
print(lps(input()))


s = input()
n = len(s)
P = [[1 if i == j else 0 for i in range(n)] for j in range(n)]
for i in range(n - 1):
	P[i][i + 1] = 2 if s[i] == s[i + 1] else 1
for x in range(2, n - 1):
	for i in range(n - x):
		j = i + x
		P[i][j] = max(P[i][j - 1], P[i + 1][j], P[i + 1][j - 1] + (2 if s[i] == s[j] else 0))
score = 0
for x in range(n - 1):
	score = max(P[0][x] * P[x + 1][n - 1], score)
print(score)


str = input()
slen = len(str)
dp = [[0 for x in range(slen)] for x in range(slen)]
for clen in range(1, slen + 1):
	for i in range(0, slen - clen + 1):
		if clen == 1:
			dp[i][i] = 1
		elif clen == 2:
			dp[i][i + 1] = 2 if str[i] == str[i + 1] else 1
		elif str[i] == str[i + clen - 1]:
			dp[i][i + clen - 1] = dp[i + 1][i + clen - 2] + 2
		else:
			dp[i][i + clen - 1] = max(dp[i + 1][i + clen - 2], dp[i + 1][i + clen - 1], dp[i][i + clen - 2])
ret = 1
for i in range(0, slen - 1):
	len1 = dp[0][i]
	len2 = dp[i + 1][slen - 1]
	ret = max(ret, len1 * len2)
print(ret)


from itertools import accumulate, islice
import operator
S = input().strip()
pals = [1] * len(S)
pals_after = [1] * len(S)
for i in reversed(range(len(S))):
	new_char = S[i]
	last_found = None
	for (j, s) in zip(reversed(range(i + 1, len(S))), reversed(S)):
		if last_found:
			new_len = max(3, pals[j] + 2)
			pals[last_found] = max(new_len, pals[last_found])
			pals_after[i] = max(new_len, pals_after[i])
		if new_char == s:
			last_found = j
			if 2 > pals[j]:
				pals[j] = 2
			if 2 > pals_after[i]:
				pals_after[i] = 2
pals[:] = accumulate(pals, max)
pals_after[::-1] = accumulate(reversed(pals_after), max)
score = max(map(operator.mul, pals, pals_after[1:]))
print(score)


word = input().strip()
n = len(word)
dp = [[0 for i in range(n)] for i in range(n)]
for i in range(0, n):
	dp[i][i] = 1
for gap in range(2, n + 1):
	for l in range(0, n - gap + 1):
		r = l + gap - 1
		if word[l] == word[r]:
			if gap == 2:
				dp[l][r] = 2
			else:
				dp[l][r] = dp[l + 1][r - 1] + 2
		else:
			dp[l][r] = max(dp[l + 1][r], dp[l][r - 1])
mx = 1
for gap in range(1, n + 1):
	for l in range(0, n - gap):
		r = gap + l - 1
		mx = max(mx, dp[l][r] * dp[r + 1][n - 1])
print(mx)


def find_lps(s):
	n = len(s)
	lps = [[0 for _ in range(n)] for _ in range(n)]
	for i in range(n):
		lps[i][i] = 1
	for sublen in range(2, n + 1):
		for i in range(n - sublen + 1):
			j = i + sublen - 1
			if s[i] == s[j]:
				lps[i][j] = lps[i + 1][j - 1] + 2
			else:
				lps[i][j] = max(lps[i + 1][j], lps[i][j - 1])
	return lps
S = input()
n = len(S)
LPS = find_lps(S)
score = max((LPS[0][i] * LPS[i + 1][n - 1] for i in range(1, n - 3)))
print(score)


str1 = input()
n = len(str1)
table = [[0 for i in range(n)] for j in range(n)]
for i in range(n):
	table[i][i] = 1
for sl in range(2, n + 1):
	for i in range(n - sl + 1):
		j = i + sl - 1
		if str1[i] == str1[j] and sl == 2:
			table[i][j] = 2
		elif str1[i] == str1[j]:
			table[i][j] = table[i + 1][j - 1] + 2
		else:
			table[i][j] = max(table[i][j - 1], table[i + 1][j])
lis1 = []
for i in range(n):
	if i + 1 < n:
		lis1.append(table[0][i] * table[i + 1][n - 1])
print(max(lis1))


def max_palindrom(str, i, j, dp):
	if i > j:
		return 0
	if dp[i][j] != None:
		return dp[i][j]
	if i == j:
		dp[i][j] = 1
		return dp[i][j]
	if str[i] == str[j]:
		dp[i][j] = 2 + max_palindrom(str, i + 1, j - 1, dp)
	else:
		dp[i][j] = max(max_palindrom(str, i + 1, j, dp), max_palindrom(str, i, j - 1, dp))
	return dp[i][j]
str = input()
dp = [[1] * len(str) for i in range(len(str))]
n = len(str)
for cl in range(2, n + 1):
	for i in range(n - cl + 1):
		j = i + cl - 1
		if str[i] == str[j] and cl == 2:
			dp[i][j] = 2
		elif str[i] == str[j]:
			dp[i][j] = dp[i + 1][j - 1] + 2
		else:
			dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])
res = 1
for i in range(n - 1):
	res = max(res, dp[0][i] * dp[i + 1][n - 1])
print(res)


def findPalindromes(word):
	length = len(word)
	i = [0] * length
	arr = [i[:] for j in range(length)]
	for i in range(length):
		arr[i][i] = 1
	for cl in range(2, length + 1):
		for i in range(length - cl + 1):
			j = i + cl - 1
			if word[i] == word[j]:
				if cl == 2:
					arr[i][j] = 2
				else:
					arr[i][j] = arr[i + 1][j - 1] + 2
			else:
				arr[i][j] = max(arr[i][j - 1], arr[i + 1][j])
	return arr

def findMaxProd(arr):
	maxProd = 1
	for i in range(len(arr) - 1):
		prod = arr[0][i] * arr[i + 1][len(arr) - 1]
		if prod > maxProd:
			maxProd = prod
	return maxProd
s = input()
print(findMaxProd(findPalindromes(s)))


def isPal(s):
	return s == s[::-1]
mem = {}
pals = {}

def getMaxPalSeq(s, start, end):
	if start == end:
		return 1
	elif isPal(s[start:end + 1]):
		pals[s[start:end + 1]] = (start, end)
		return end - start + 1
	else:
		if (start, end) in mem:
			return mem[start, end]
		else:
			mem[start, end] = max(getMaxPalSeq(s, start + 1, end), getMaxPalSeq(s, start, end - 1))
		return mem[start, end]

def getMaxPal2(s, i, j):
	if i == j:
		return 1
	elif s[i] == s[j] and i + 1 == j:
		return 2
	elif (i, j) in mem:
		return mem[i, j]
	elif s[i] == s[j]:
		mem[i, j] = getMaxPal2(s, i + 1, j - 1) + 2
	else:
		mem[i, j] = max(getMaxPal2(s, i + 1, j), getMaxPal2(s, i, j - 1))
	return mem[i, j]

def getMaxPalNR(s, n):
	global dp
	dp = [[0] * n for i in range(n)]
	for i in range(n):
		dp[i][i] = 1
	for i in range(1, n):
		for j in range(0, n - i):
			s1 = j
			s2 = j + i
			if s1 + 1 == s2 and s[s1] == s[s2]:
				dp[s1][s2] = 2
			elif s[s1] == s[s2]:
				dp[s1][s2] = dp[s1 + 1][s2 - 1] + 2
			else:
				dp[s1][s2] = max(dp[s1][s2 - 1], dp[s1 + 1][s2])
	return dp[0][n - 1]

def solution(s):
	global dp
	n = len(s)
	maxScore = 0
	getMaxPalNR(s, n)
	for i in range(n - 1):
		s1 = dp[0][i]
		s2 = dp[i + 1][n - 1]
		if s1 * s2 > maxScore:
			maxScore = s1 * s2
	print(maxScore)
s = str(input())
solution(s)


def solve(s):
	l = len(s)
	dp = [[0] * l for _ in range(l)]
	for k in range(l):
		dp[k][k] = 1
	for d in range(1, l - 1):
		for i in range(l - d):
			j = i + d
			if s[i] == s[j]:
				dp[i][j] = 2 + dp[i + 1][j - 1]
			else:
				dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
	res = 0
	for m in range(l - 1):
		a = dp[0][m]
		b = dp[m + 1][l - 1]
		res = max(res, a * b)
	return res
s = input()
r = solve(s)
print(r)


S = 'eeegeeksforskeeggeeks'
S = input()[:3000]
N = len(S)
L = [None] * N
for i in range(N):
	L[i] = [None] * N
	L[i][i] = 1
for sublen in range(2, N + 1):
	for i in range(N - sublen + 1):
		j = i + sublen - 1
		if S[i] == S[j] and sublen == 2:
			L[i][j] = 2
		elif S[i] == S[j]:
			L[i][j] = L[i + 1][j - 1] + 2
		else:
			L[i][j] = max(L[i + 1][j], L[i][j - 1])
Ai = 0
Bj = N - 1
vals = []
for Aj in range(N - 1):
	Bi = Aj + 1
	val = L[Ai][Aj] * L[Bi][Bj]
	vals.append(val)
print(max(vals))


def max_palindromic_ss(s, i, j):
	if (i, j) in cache_1:
		return cache_1[i, j]
	if i == j:
		return 1
	if i + 1 == j and s[i] == s[j]:
		return 2
	if s[i] == s[j]:
		ret = 2 + max_palindromic_ss(s, i + 1, j - 1)
	else:
		ret = max(max_palindromic_ss(s, i + 1, j), max_palindromic_ss(s, i, j - 1))
	if (i, j) not in cache_1:
		cache_1[i, j] = ret
	return ret
s = input()
n = len(s)
LPS = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
	LPS[i][i] = 1
for window in range(2, n + 1):
	for i in range(n - window + 1):
		j = i + window - 1
		if window == 2 and s[i] == s[j]:
			LPS[i][j] = 2
		elif s[i] == s[j]:
			LPS[i][j] = 2 + LPS[i + 1][j - 1]
		else:
			LPS[i][j] = max(LPS[i][j - 1], LPS[i + 1][j])
R = [0 for _ in range(n)]
for i in range(1, n - 1):
	R[i] = LPS[0][i] * LPS[i + 1][n - 1]
print(max(R))


S = input()
n = len(S)
LPS = [[1] * n for _ in range(n)]
for i in range(1, n):
	if S[i - 1] == S[i]:
		LPS[i - 1][i] = 2
for k in range(2, n):
	i = 0
	j = k
	while j < n:
		LPS[i][j] = max(LPS[i][j - 1], LPS[i + 1][j], LPS[i + 1][j - 1] + 2 if S[i] == S[j] else 0)
		i += 1
		j += 1
best = 0
for i in range(n - 1):
	best = max(best, LPS[0][i] * LPS[i + 1][n - 1])
print(best)


import sys
S = sys.stdin.readline().strip()
n = len(S)
dp = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
	dp[i][i] = 1
for length in range(2, n + 1):
	for i in range(n + 1 - length):
		j = i + length - 1
		if S[i] == S[j] and length == 2:
			dp[i][j] = 2
		elif S[i] == S[j]:
			dp[i][j] = dp[i + 1][j - 1] + 2
		else:
			dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])
best = 0
for i in range(1, n):
	best = max(best, dp[0][i - 1] * dp[i][n - 1])
print(best)


s = input()
n = len(s)
m = []
for i in range(n):
	u = []
	for j in range(n):
		u.append(0)
	m.append(u)
for i in range(n):
	for j in range(n):
		if i + j == n:
			break
		if i == 0:
			m[i][j] = 1
		elif i == 1:
			m[i][j] = 1
			if s[j] == s[j + i]:
				m[i][j] = 2
		else:
			tmp = 0
			if s[j] == s[j + i]:
				tmp = 2
			m[i][j] = max(m[i - 2][j + 1] + tmp, m[i - 1][j], m[i - 1][j + 1])
r = 0
for i in range(0, n - 1):
	r = max(r, m[i][0] * m[n - i - 2][i + 1])
print(r)


def build(s):
	l = len(s)
	dp = [[0 for i in range(l + 1)] for j in range(l + 1)]
	for j in range(1, l + 1):
		dp[1][j] = 1
	for i in range(2, l + 1):
		for j in range(0, l - i + 1):
			if s[j] == s[j + i - 1]:
				dp[i][j + 1] = 2 + dp[i - 2][j + 2]
			else:
				dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j + 2])
	return dp

def solve(s):
	dp = build(s)
	maxv = 0
	for i in range(1, len(s) - 1):
		maxv = max(maxv, dp[i][1] * dp[len(s) - i][i + 1])
	return maxv
s = input()
print(solve(s))


def lps(str):
	n = len(str)
	L = [[0 for x in range(n)] for x in range(n)]
	for i in range(n):
		L[i][i] = 1
	for cl in range(2, n + 1):
		for i in range(n - cl + 1):
			j = i + cl - 1
			if str[i] == str[j] and cl == 2:
				L[i][j] = 2
			elif str[i] == str[j]:
				L[i][j] = L[i + 1][j - 1] + 2
			else:
				L[i][j] = max(L[i][j - 1], L[i + 1][j])
	scorearr = [L[0][i] * L[i + 1][n - 1] for i in range(n - 1)]
	return max(scorearr)
seq = input()
print(lps(seq))


def max_score(s):
	n = len(s)
	table = [[0] * n for i in range(n)]
	for x in range(n):
		(i, j) = (0, x)
		for y in range(n - x):
			if i == j:
				table[i][j] = 1
			elif s[i] == s[j]:
				table[i][j] = 2 + table[i + 1][j - 1]
			else:
				table[i][j] = max(table[i + 1][j], table[i][j - 1])
			(i, j) = (i + 1, j + 1)
	return max((table[0][i - 1] * table[i][n - 1] for i in range(1, n)))
s = input().strip()
print(max_score(s))


import sys
sys.setrecursionlimit(1000000)
s = list(input())
n = len(s)
pal = [[-1 for j in range(n)] for i in range(n)]

def rec(i, j):
	if pal[i][j] != -1:
		return pal[i][j]
	if i == j:
		pal[i][j] = 1
	elif j == i + 1:
		if s[i] == s[j]:
			pal[i][j] = 2
		else:
			pal[i][j] = 1
	elif i < j:
		if s[i] == s[j]:
			pal[i][j] = rec(i + 1, j - 1) + 2
		else:
			pal[i][j] = max(rec(i, j - 1), rec(i + 1, j))
	return pal[i][j]
pro = 1
for i in range(0, n - 1):
	temp = rec(0, i) * rec(i + 1, n - 1)
	if pro < temp:
		pro = temp
print(pro)


def LPS_maxprod(s):
	LPS = [[0] * len(s) for _ in range(len(s))]
	for i in range(len(s)):
		LPS[i][i] = 1
	for length in range(2, len(s) + 1):
		for i in range(len(s) - length + 1):
			j = i + length - 1
			if s[i] == s[j]:
				LPS[i][j] = 2 + (0 if length == 2 else LPS[i + 1][j - 1])
			else:
				LPS[i][j] = max(LPS[i][j - 1], LPS[i + 1][j])
	return max((LPS[0][i] * LPS[i + 1][-1] for i in range(len(s) - 1)))
s = input()
print(LPS_maxprod(s))


S = input()
n = len(S)
dp = [[0 for j in range(n)] for i in range(n + 1)]
for i in range(n):
	dp[1][i] = 1
for i in range(2, n + 1):
	for j in range(n - i + 1):
		if S[j] == S[j + i - 1]:
			dp[i][j] = dp[i - 2][j + 1] + 2
		else:
			dp[i][j] = max(dp[i - 1][j], dp[i - 1][j + 1])
maxi = -1
for i in range(n):
	if maxi < dp[i][0] * dp[n - i][i]:
		maxi = dp[i][0] * dp[n - i][i]
print(maxi)


class Palindrome:

	def __init__(self, string: str):
		self.string = string

	@property
	def combos(self):
		n = len(self.string)
		combos = []
		for x in range(n):
			ini = [1] * n
			combos.append(ini)
		for i in range(1, n):
			for j in range(n - i):
				if i == 1:
					if self.string[j] == self.string[i + j]:
						combos[j][i + j] = 2
					else:
						combos[j][i + j] = 1
				elif self.string[j] == self.string[i + j]:
					combos[j][i + j] = combos[j + 1][i + j - 1] + 2
				else:
					combos[j][i + j] = max(combos[j + 1][i + j], combos[j][i + j - 1])
		return combos

	@property
	def max_subsq(self):
		max_score = 0
		combos = self.combos
		for i in range(0, len(self.string) - 1):
			score = combos[0][i] * combos[i + 1][len(self.string) - 1]
			max_score = score if score > max_score else max_score
		return max_score
s = input()
print(Palindrome(s).max_subsq)


import os
import sys

def lp(i, j):
	global dp
	if i == j:
		dp[i][j] = 1
		return 1
	elif dp[i][j] > 0:
		return dp[i][j]
	elif j == i + 1:
		if s[i] == s[j]:
			dp[i][j] = 2
			return 2
		else:
			dp[i][j] = 1
			return 1
	res = 0
	if s[i] == s[j]:
		res = 2 + lp(i + 1, j - 1)
	else:
		res = max(lp(i + 1, j), lp(i, j - 1))
	dp[i][j] = res
	return res

def playWithWords():
	l = len(s)
	if l == 1:
		return 0
	elif l == 2:
		return 1
	global dp
	dp = [[0 for i in range(l)] for j in range(l)]
	for i in range(l):
		(a, b) = (i, min(l - 1, 500 + i))
		lp(a, b)
	for i in range(l):
		(a, b) = (i, min(l - 1, 1000 + i))
		lp(a, b)
	for i in range(l):
		(a, b) = (i, min(l - 1, 1500 + i))
		lp(a, b)
	for i in range(l):
		(a, b) = (i, min(l - 1, 2000 + i))
		lp(a, b)
	mid = l // 2
	for i in range(l // 2 + 1):
		(a, b) = (max(0, mid - i), min(l - 1, mid + i))
		lp(a, b)
	for i in range(l):
		(a, b) = (i, min(l - 1, mid + i))
		lp(a, b)
	res = 0
	for i in range(1, l - 1):
		res = max(res, lp(0, i) * lp(i + 1, l - 1))
	return res
s = input()
result = playWithWords()
print(result)


def palindromic_string(string):
	n = len(string)
	l = [[0 for x in range(n)] for y in range(n)]
	for i in range(n):
		for j in range(n):
			if i + j == n:
				break
			if i == 0:
				l[i][j] = 1
			elif i == 1:
				l[i][j] = 1
				if string[j] == string[i + j]:
					l[i][j] = 2
			else:
				temp = 0
				if string[j] == string[i + j]:
					temp = 2
				l[i][j] = max(l[i - 2][j + 1] + temp, l[i - 1][j], l[i - 1][j + 1])
	r = 0
	for x in range(0, len(string) - 1):
		r = max(r, l[x][0] * l[len(string) - x - 2][1 + x])
	return r
string = input().strip()
print(palindromic_string(string))


s = input()
n = len(s)
m = []
for i in range(n):
	u = []
	for j in range(n):
		u.append(0)
	m.append(u)
for i in range(n):
	for j in range(n):
		if i + j == n:
			break
		if i == 0:
			m[i][j] = 1
		elif i == 1:
			m[i][j] = 1
			if s[j] == s[j + i]:
				m[i][j] = 2
		else:
			tmp = 0
			if s[j] == s[j + i]:
				tmp = 2
			m[i][j] = max(m[i - 2][j + 1] + tmp, m[i - 1][j], m[i - 1][j + 1])
r = 0
for i in range(0, n - 1):
	r = max(r, m[i][0] * m[n - i - 2][i + 1])
print(r)


import sys
sys.setrecursionlimit(10 ** 8)

def solve(i, j, string, dp):
	if i > j:
		dp[i][j] = 0
		return 0
	if i == j:
		dp[i][j] = 1
		return 1
	if dp[i][j] != None:
		return dp[i][j]
	if string[i] == string[j]:
		take = solve(i + 1, j - 1, string, dp) + 2
		skipl = solve(i + 1, j, string, dp)
		skipr = solve(i, j - 1, string, dp)
		dp[i][j] = max(take, skipl, skipr)
	else:
		skipl = solve(i + 1, j, string, dp)
		skipr = solve(i, j - 1, string, dp)
		dp[i][j] = max(skipl, skipr)
	return dp[i][j]

def run(string, n):
	if n == 1:
		return 1
	dp = [[None for i in range(n)] for j in range(n)]
	solve(0, n - 1, string, dp)
	answer = 0
	for i in range(n - 1):
		answer = max(answer, dp[0][i] * dp[i + 1][n - 1])
	return answer
string = input()
n = len(string)
print(run(string, n))


S = input().rstrip()
n = len(S)
D = [None] * n
(D[0], D[1]) = ([1] * n, [1 if S[i] != S[i + 1] else 2 for i in range(0, n - 1)])
for i in range(2, n):
	D[i] = [None] * (n - i)
for i in range(2, n):
	(A_2, A_1, A) = (D[i - 2], D[i - 1], D[i])
	for j in range(0, n - i):
		A[j] = max(A_2[j + 1] + (2 if S[j] == S[j + i] else 0), A_1[j], A_1[j + 1])
print(max(map(lambda i: D[i][0] * D[n - i - 2][i + 1], range(n - 1))))


s = input()
n = len(s)
m = []
for i in range(n):
	u = []
	for j in range(n):
		u.append(0)
	m.append(u)
for i in range(n):
	for j in range(n):
		if i + j == n:
			break
		if i == 0:
			m[i][j] = 1
		elif i == 1:
			m[i][j] = 1
			if s[j] == s[j + i]:
				m[i][j] = 2
		else:
			tmp = 0
			if s[j] == s[j + i]:
				tmp = 2
			m[i][j] = max(m[i - 2][j + 1] + tmp, m[i - 1][j], m[i - 1][j + 1])
r = 0
for i in range(0, n - 1):
	r = max(r, m[i][0] * m[n - i - 2][i + 1])
print(r)


def getTheProduct(s):
	length = len(s)
	temp = [[0 for i in range(length)] for j in range(length)]
	for i in range(length):
		temp[i][i] = 1
	for l in range(2, length + 1):
		for i in range(0, length - l + 1):
			j = i + l - 1
			if s[i] == s[j] and j == i + 1:
				temp[i][j] = 2
			elif s[i] == s[j]:
				temp[i][j] = temp[i + 1][j - 1] + 2
			else:
				temp[i][j] = max(temp[i + 1][j], temp[i][j - 1])
	product = -9999
	for i in range(0, length):
		left = 0
		right = 0
		left = getMaximum(temp[0][0:i])
		right = getMaximum(temp[i][i:])
		maxValue = left * right
		if maxValue > product:
			product = maxValue
	return product

def getMaximum(arr):
	l = len(arr)
	max = -99
	for i in range(l):
		if arr[i] > max:
			max = arr[i]
	return max
s = input()
result = getTheProduct(s)
print(result)


def findMaxSubsequence(seq):
	length = len(seq)
	seqLength = [[0 for i in range(length)] for j in range(length)]
	for i in range(length):
		seqLength[i][i] = 1
	for cols in range(2, length + 1):
		for i in range(0, length - cols + 1):
			j = i + cols - 1
			if seq[i] == seq[j]:
				if cols == 2:
					seqLength[i][j] = 2
				else:
					seqLength[i][j] = seqLength[i + 1][j - 1] + 2
			else:
				seqLength[i][j] = max(seqLength[i + 1][j], seqLength[i][j - 1])
	return seqLength
string = list(input())
seqLength = findMaxSubsequence(string)
maxScore = 0
for i in range(0, len(string) - 1):
	left = seqLength[0][i]
	right = seqLength[i + 1][-1]
	score = left * right
	if score > maxScore:
		maxScore = score
print(maxScore)


s = input()
n = len(s)
dp = [[-1] * n for _ in range(n)]
for l in range(n - 1, -1, -1):
	for r in range(l, n):
		if l < n - 1 and l < r:
			dp[l][r] = max(dp[l][r], dp[l + 1][r])
		if r > 0 and r > l:
			dp[l][r] = max(dp[l][r], dp[l][r - 1])
		if s[l] == s[r]:
			if l < r - 1:
				dp[l][r] = max(dp[l][r], 2 + dp[l + 1][r - 1])
			elif l < r:
				dp[l][r] = max(dp[l][r], 2)
			else:
				dp[l][r] = max(dp[l][r], 1)
result = 0
for i in range(n - 1):
	result = max(result, dp[0][i] * dp[i + 1][n - 1])
print(result)


s = input()
n = len(s)
m = []
for i in range(n):
	u = []
	for j in range(n):
		u.append(0)
	m.append(u)
for i in range(n):
	for j in range(n):
		if i + j == n:
			break
		if i == 0:
			m[i][j] = 1
		elif i == 1:
			m[i][j] = 1
			if s[j] == s[j + i]:
				m[i][j] = 2
		else:
			tmp = 0
			if s[j] == s[j + i]:
				tmp = 2
			m[i][j] = max(m[i - 2][j + 1] + tmp, m[i - 1][j], m[i - 1][j + 1])
r = 0
for i in range(0, n - 1):
	r = max(r, m[i][0] * m[n - i - 2][i + 1])
print(r)