Alice and Bob are playing a game using a string S of length N. They both have their individual strings which are initially empty.

Both players take alternate turns. Alice starts first.  
In Alice's turn, she will:
Choose a prefix of S;
Remove the chosen prefix from S;
Append the prefix to the end of her string. 

In Bob's turn, he will:
Choose a suffix of S;
Remove the chosen suffix from S;
Reverse the suffix and append it to the end of his string.

Chef has decided to reward them if the length of the *Longest Common Subsequence* (LCS) of Alice's and Bob's strings is maximized. Help Chef calculate the length of maximum LCS that can be achieved by Alice and Bob.

Note:
A prefix is obtained by deleting some (possibly zero) elements from the end of the string.
A suffix is obtained by deleting some (possibly zero) elements from the beginning of the string.
Please use fast I/O for input and pypy for python submissions.

------ Input Format ------ 

- The first line of input will contain a single integer T, denoting the number of test cases.
- Each test case consists of two lines, the first line contains a single integer N denoting the length of the original string.
- The second line contains the original string S. 

------ Output Format ------ 

For each test case, output the length of the maximum LCS achievable by Alice and Bob.

------ Constraints ------ 

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 5000$
- The sum of $N$ over all test cases won't exceed $5000$.

----- Sample Input 1 ------ 
3
4
abab
6
abccda
4
aaaa

----- Sample Output 1 ------ 
1
2
2

----- explanation 1 ------ 
Test case $1$: In Alice's turn, she can pick the prefix $S[1, 2] =$ ab, and append it to her string. Thus, the remaining string is ab. In Bob's turn, he can pick the suffix $S[1, 2] =$ ab, reverse it, and append to his string.  
Thus, Alice's string is ab, and, Bob's string is ba. The length of the longest common subsequence in these two strings is $1$.

Test case $2$: In Alice's turn, she can pick the prefix $S[1, 3] =$ abc, and append it to her string. Thus, the remaining string is cda. In Bob's turn, he can pick the suffix $S[1, 3] =$ cda, reverse it, and append to his string.  
Thus, Alice's string is abc, and, Bob's string is adc. The length of the longest common subsequence in these two strings is $2$.

Test case $3$: In Alice's turn, she can pick the prefix $S[1, 2] =$ aa, and append it to her string. Thus, the remaining string is aa. In Bob's turn, he can pick the suffix $S[1, 2] =$ aa, reverse it, and append to his string.  
Thus, Alice's string is aa, and, Bob's string is aa. The length of the longest common subsequence in these two strings is $2$.

Difficulty: MEDIUM
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
def lcs(s, r):
	(n, m) = (len(s), len(r))
	(prev, curr) = ([0] * (m + 1), [0] * (m + 1))
	for i in range(1, n + 1):
		for j in range(1, m + 1):
			if s[i - 1] == r[j - 1]:
				curr[j] = 1 + prev[j - 1]
			elif curr[j - 1] > prev[j]:
				curr[j] = curr[j - 1]
			else:
				curr[j] = prev[j]
		(curr, prev) = (prev, curr)
	return prev[m]
t = int(input())
for i in range(t):
	n = int(input())
	s = input()
	r = s[::-1]
	print(lcs(s, r) // 2)


def lcss(s1, s2):
	(m, n) = (len(s1), len(s2))
	(prev, cur) = ([0] * (n + 1), [0] * (n + 1))
	for i in range(1, m + 1):
		for j in range(1, n + 1):
			if s1[i - 1] == s2[j - 1]:
				cur[j] = 1 + prev[j - 1]
			elif cur[j - 1] > prev[j]:
				cur[j] = cur[j - 1]
			else:
				cur[j] = prev[j]
		(cur, prev) = (prev, cur)
	return prev[n]
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	b = s[::-1]
	print(lcss(s, b) // 2)


def solve(s, n):
	dp = [[0] * n for _ in range(n)]
	for i in range(n - 1, -1, -1):
		dp[i][i] = 1
		for j in range(i + 1, n):
			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])
	return dp[0][n - 1] // 2
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	result = solve(s, n)
	print(result)


def lcs(str1, str2):
	(mad, new) = (len(str1), len(str2))
	(previous, current) = ([0] * (new + 1), [0] * (new + 1))
	for i in range(1, mad + 1):
		for j in range(1, new + 1):
			if str1[i - 1] == str2[j - 1]:
				current[j] = 1 + previous[j - 1]
			elif current[j - 1] > previous[j]:
				current[j] = current[j - 1]
			else:
				current[j] = previous[j]
		(current, previous) = (previous, current)
	return previous[new]
for i in range(int(input())):
	n = int(input())
	s1 = input()
	s2 = s1[::-1]
	print(lcs(s1, s2) // 2)


def lcs(s1, s2):
	(m, n) = (len(s1), len(s2))
	(prev, cur) = ([0] * (n + 1), [0] * (n + 1))
	for i in range(1, m + 1):
		for j in range(1, n + 1):
			if s1[i - 1] == s2[j - 1]:
				cur[j] = 1 + prev[j - 1]
			elif cur[j - 1] > prev[j]:
				cur[j] = cur[j - 1]
			else:
				cur[j] = prev[j]
		(cur, prev) = (prev, cur)
	return prev[n]
for i in range(int(input())):
	c = int(input())
	b = input()
	f = b[::-1]
	g = c
	print(lcs(b, b[::-1]) // 2)


def lcs(X, Y):
	m = n = len(Y)
	mx = 0
	L = [[0] * (n + 1) for i in range(m + 1)]
	for i in range(1, m + 1):
		for j in range(1, n - i + 2):
			if i == 0 or j == 0:
				L[i][j] = 0
			elif X[i - 1] == Y[j - 1]:
				L[i][j] = L[i - 1][j - 1] + 1
			else:
				L[i][j] = max(L[i - 1][j], L[i][j - 1])
			if i + j == n:
				mx = max(mx, L[i][j])
	return mx
for _ in range(int(input())):
	n = int(input())
	l = input()
	s = l[::-1]
	print(lcs(l, s))


def solve(n, s):
	s = '!' + s + '!'
	dp = [[0] * (n + 2) for i in range(n + 2)]
	for i in range(1, n + 1):
		for j in reversed(range(i + 1, n + 1)):
			dp[i][j] = max(dp[i - 1][j], dp[i][j + 1])
			if s[i] == s[j]:
				dp[i][j] = max(dp[i][j], dp[i - 1][j + 1] + 1)
	ans = max([dp[i][i + 1] for i in range(1, n)])
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	s = input()
	print(solve(n, s))


def solve(s, s1):
	mx = 0
	l = [[0] * (n + 1) for i in range(n + 1)]
	for i in range(1, n + 1):
		for j in range(1, n - i + 2):
			if s[i - 1] == s1[j - 1]:
				l[i][j] = 1 + l[i - 1][j - 1]
			else:
				l[i][j] = max(l[i - 1][j], l[i][j - 1])
			if i + j == n:
				mx = max(mx, l[i][j])
	print(mx)
for _ in range(int(input())):
	n = int(input())
	s = input()
	s1 = ''.join(reversed(s))
	solve(s, s1)


t = int(input())

def solve(n, x):
	(a, b) = (x, ''.join(reversed(list(x))))
	dp = [[0] * (n + 1) for i in range(n + 1)]
	mx = 0
	for i in range(1, n + 1):
		for j in range(1, n - i + 2):
			if a[i - 1] == b[j - 1]:
				dp[i][j] = dp[i - 1][j - 1] + 1
			else:
				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
			if i + j == n:
				mx = max(mx, dp[i][j])
	return mx
for _ in range(t):
	n = int(input())
	x = input()
	print(solve(n, x))


def lps(s):
	n = len(s)
	a = [0] * n
	for i in range(n - 1, -1, -1):
		back_up = 0
		for j in range(i, n):
			if j == i:
				a[j] = 1
			elif s[i] == s[j]:
				temp = a[j]
				a[j] = back_up + 2
				back_up = temp
			else:
				back_up = a[j]
				a[j] = max(a[j - 1], a[j])
	return a[n - 1]
for aa in range(int(input())):
	n = int(input())
	s = input()
	d = {}
	for i in s:
		if i in d:
			d[i] += 1
		else:
			d[i] = 1
	a = ''
	for i in s:
		if d[i] > 1:
			a += i
	s = a[:]
	n = len(s)
	if n == 0:
		print(0)
		continue
	if n <= 3:
		print(1)
		continue
	k = s[::-1]
	x = []
	u = lps(s)
	print(u // 2)


from bisect import bisect_left

def solve():
	n = int(input())
	s = input()
	t1 = s
	t2 = s[::-1]
	n2 = len(t2)
	d2 = dict()
	for i in range(n2 - 1, -1, -1):
		c = t2[i]
		if c not in d2:
			d2[c] = []
		d2[c].append(i)
	s = []
	for c in t1:
		if c in d2:
			for i in d2[c]:
				j = bisect_left(s, i)
				if j == len(s):
					s.append(i)
				else:
					s[j] = i
	return len(s) // 2
t = int(input())
while t:
	print(solve())
	t -= 1


import sys

def lcs(s1, s2):
	(m, n) = (len(s1), len(s2))
	(prev, cur) = ([0] * (n + 1), [0] * (n + 1))
	for i in range(1, m + 1):
		for j in range(1, n + 1):
			if s1[i - 1] == s2[j - 1]:
				cur[j] = 1 + prev[j - 1]
			elif cur[j - 1] > prev[j]:
				cur[j] = cur[j - 1]
			else:
				cur[j] = prev[j]
		(cur, prev) = (prev, cur)
	return prev[n]

def get_string():
	return sys.stdin.readline().strip()
for _ in range(int(input())):
	a = int(input())
	s = get_string()
	l1 = s
	l2 = s[::-1]
	sys.stdout.write(str(lcs(l1, l2) // 2) + '\n')


def LCS(S, n):
	if S == S[::-1]:
		return len(S)
	P = [0] * n
	for i in range(n - 1, -1, -1):
		Dp = P[:]
		Dp[i] = 1
		for j in range(i + 1, n):
			if S[i] == S[j]:
				Dp[j] = 2 + P[j - 1]
			else:
				Dp[j] = max(P[j], Dp[j - 1])
		P = Dp
	return Dp[n - 1]
from math import gcd
test_case = int(input())
for test in range(test_case):
	n = int(input())
	S = input()
	A = LCS(S, n)
	print(A // 2)


import collections
import math
import random
import sys
from functools import *
from heapq import *
input = lambda : sys.stdin.readline().rstrip('\r\n')
ints = lambda : list(map(int, input().split()))

def solve() -> None:
	n = int(input())
	s = input()
	dp = [[0] * n for _ in range(n)]
	for i in range(n - 1, -1, -1):
		dp[i][i] = 1
		for j in range(i + 1, n):
			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])
	print(dp[0][n - 1] // 2)
t = int(input())
for _ in range(t):
	solve()


for t in range(int(input())):

	def func(s: str):
		dp = [[0] * len(s) for _ in range(len(s))]
		for k in range(len(s)):
			for i in range(len(s) - k):
				j = k + i
				if i == j:
					dp[i][j] = 1
				elif 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])
		return dp[0][-1]
	N = int(input())
	S = input()
	print(func(S) // 2)