Given a linked list, the task is to complete the function maxPalindrome() which returns an integer denoting  the length of the longest palindrome list that exist in the given linked list.
Input:
The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. The first line of each test case contains an integer N denoting the size of the linked list . Then in the next line are N space separated values of the given linked list.
Output:
For each test case output will be the required max length of the palindrome present in the given linked list.
User Task:
The task is to complete the function maxPalindrome() which should count the length of longest palindrome in the given list and return it.
Constraints:
1 <= T <= 100
1 <= N <= 100
Example:
Input:
2
7
2 3 7 3 2 12 24
5
12 4 4 3 14
Output:
5
2
Explanation:
Testcase 1: 2 -> 3 -> 7 -> 3 -> 2 is the linked list whose nodes leads to a palindrome as 2 3 7 3 2.

Difficulty: MEDIUM
Tags: String algorithms

Data structures
Skill types: Data structures

Starter code:
# your task is to complete this function

# function should return an integer

'''

class node:

    def __init__(self):

        self.data = None

        self.next = Non

'''

class Solution:

    def maxPalindrome(self,head):

        # Code here



Solutions:
class Solution:

	def maxPalindrome(self, head):
		prev = None
		curr = head
		res = 0
		while curr:
			nxt = curr.next
			curr.next = prev
			res = max(res, 2 * self.val(prev, nxt) + 1)
			res = max(res, 2 * self.val(curr, nxt))
			prev = curr
			curr = nxt
		return res

	def val(self, rt1, rt2):
		f = rt1
		s = rt2
		c = 0
		while f and s:
			if f.data == s.data:
				c += 1
				f = f.next
				s = s.next
			else:
				break
		return c


def check(s):
	if s == s[::-1]:
		return True
	return False

class Solution:

	def maxPalindrome(self, head):
		if head == None:
			return
		lis = []
		temp = head
		while temp:
			lis.append(temp.data)
			temp = temp.next
		dp = {}
		n = [len(lis)] * 1
		ans = [0] * 1

		def fun(i, j, s):
			if i >= j:
				return 1
			if (i, j) in dp:
				return dp[i, j]
			if check(s[i:j + 1]):
				return j - i + 1
			dp[i, j] = max(fun(i + 1, j, s), fun(i, j - 1, s))
			return dp[i, j]
		t = fun(0, len(lis) - 1, lis)
		return t


class Solution:

	def maxPalindrome(self, head):
		n = head
		L = []
		while n is not None:
			L.append(n.data)
			n = n.next
		x = []
		while L:
			a = L.copy()
			while a:
				b = a.copy()
				b.reverse()
				if a == b:
					x.append(len(a))
					break
				a.pop()
			L.pop(0)
		return max(x)


class Solution:

	def maxPalindrome(self, head):
		prev_point = None
		current_point = head
		next_point = head.next
		ans = 0
		while current_point != None:
			current_point.next = prev_point
			size = 1
			temp_prev = prev_point
			temp_next = next_point
			while temp_prev != None and temp_next != None and (temp_prev.data == temp_next.data):
				size += 2
				temp_prev = temp_prev.next
				temp_next = temp_next.next
			ans = max(ans, size)
			size = 0
			if current_point != None and next_point != None and (current_point.data == next_point.data):
				size += 2
				temp_prev = prev_point
				temp_next = next_point.next
				while temp_prev != None and temp_next != None and (temp_prev.data == temp_next.data):
					size += 2
					temp_prev = temp_prev.next
					temp_next = temp_next.next
			ans = max(ans, size)
			prev_point = current_point
			current_point = next_point
			if next_point != None:
				next_point = next_point.next
		return ans


class Solution:

	def maxPalindrome(self, head):
		(l, l2) = ([], [])
		while head != None:
			l.append(head.data)
			head = head.next
		for i in range(0, len(l)):
			for j in range(i, len(l) + 1):
				a = list(l[i:j])
				if a == a[::-1] and a != [] and (len(a) >= 1):
					l2.append(len(l[i:j]))
		return max(l2)


class Solution:

	def maxPalindrome(self, head):
		d = []
		p = head
		while p:
			d.append(p.data)
			p = p.next
		n = len(d)
		ans = 1
		dp = [[0 for i in range(n)] for j in range(n)]
		for i in range(n):
			dp[i][i] = 1
		for i in range(n - 1):
			if d[i] == d[i + 1]:
				dp[i][i + 1] = 1
				ans = 2
		for k in range(2, n):
			for i in range(0, n - k):
				j = i + k
				if d[i] == d[j] and dp[i + 1][j - 1] == 1:
					dp[i][j] = 1
					ans = max(ans, j - i + 1)
		return ans
		return ans


def countCommon(a, b):
	count = 0
	while a != None and b != None:
		if a.data == b.data:
			count = count + 1
		else:
			break
		a = a.next
		b = b.next
	return count

def maxPalindromee(head):
	result = 0
	prev = None
	curr = head
	while curr != None:
		next = curr.next
		curr.next = prev
		result = max(result, 2 * countCommon(prev, next) + 1)
		result = max(result, 2 * countCommon(curr, next))
		prev = curr
		curr = next
	return result

class Solution:

	def maxPalindrome(self, head):
		return maxPalindromee(head)


class Solution:

	def maxPalindrome(self, head):

		def count(a, b):
			res = 0
			while a and b:
				if a.data == b.data:
					res += 1
				else:
					break
				a = a.next
				b = b.next
			return res
		res = 0
		(curr, prev) = (head, None)
		while curr:
			nxt = curr.next
			curr.next = prev
			res = max(res, 2 * count(curr, nxt))
			res = max(res, 2 * count(prev, nxt) + 1)
			prev = curr
			curr = nxt
		return res


class Solution:

	def countPal(self, h1, h2):
		count = 0
		while h1 and h2:
			if h1.data == h2.data:
				count += 1
			else:
				break
			h1 = h1.next
			h2 = h2.next
		return count

	def maxPalindrome(self, head):
		prev = None
		curr = head
		res = 0
		while curr:
			nxt = curr.next
			curr.next = prev
			res = max(res, 2 * self.countPal(curr, nxt))
			res = max(res, 2 * self.countPal(prev, nxt) + 1)
			prev = curr
			curr = nxt
		return res


class Solution:

	def maxPalindrome(self, head):
		data = list()
		temp = head
		while temp:
			data.append(temp.data)
			temp = temp.next
		ans = 1
		n = len(data)
		for i in range(n):
			left = i - 1
			right = i + 1
			count1 = 1
			while left >= 0 and right < n and (data[left] == data[right]):
				left -= 1
				right += 1
				count1 += 2
			left = i
			right = i + 1
			count2 = 0
			while left >= 0 and right < n and (data[left] == data[right]):
				left -= 1
				right += 1
				count2 += 2
			ans = max(ans, count1, count2)
		return ans


class Solution:

	def countCommon(self, l1, l2):
		count = 0
		while l1 and l2 and (l1.data == l2.data):
			count += 1
			l1 = l1.next
			l2 = l2.next
		return 2 * count

	def maxPalindrome(self, head):
		(prev, next) = (None, None)
		maxSoFar = 0
		while head:
			el = self.countCommon(head, prev)
			ol = self.countCommon(head.next, prev) + 1
			maxSoFar = max(maxSoFar, el, ol)
			next = head.next
			head.next = prev
			prev = head
			head = next
		return maxSoFar


class Solution:

	def maxPalindrome(self, head):
		opt = []
		res = []
		while head:
			opt.append(head.data)
			head = head.next
		for i in range(len(opt)):
			for j in range(i + 1, len(opt)):
				if opt[i:j + 1] == opt[i:j + 1][::-1]:
					res.append(len(opt[i:j + 1]))
		return max(res) if res else 1


class Solution:

	def maxPalindrome(self, head):
		s = []
		while head:
			s.append(head.data)
			head = head.next
		if s == s[::-1]:
			return len(s)
		(start, size) = (0, 1)
		for i in range(1, len(s)):
			(l, r) = (i - size, i + 1)
			(s1, s2) = (s[l - 1:r], s[l:r])
			if l >= 1 and s1 == s1[::-1]:
				size += 2
				start = l - 1
			elif s2 == s2[::-1]:
				size += 1
				start = l
		return len(s[start:start + size])


class Solution:

	def maxPalindrome(self, head):
		a1 = {}
		t1 = head
		prev = None
		while t1 != None:
			a1[t1] = prev
			prev = t1
			t1 = t1.next
		c = 0
		t = head
		while t != None:
			t1 = t
			t2 = t
			c2 = 1
			while t1 != None and t2 != None and (t1.data == t2.data):
				c = max(c, c2)
				c2 += 2
				t1 = a1[t1]
				t2 = t2.next
			t1 = t
			t2 = t.next
			c2 = 2
			while t2 != None and t1 != None and (t1.data == t2.data):
				c = max(c, c2)
				c2 += 2
				t1 = a1[t1]
				t2 = t2.next
			t = t.next
		return c


class Solution:

	def maxPalindrome(self, head):

		def common(head1, head2):
			c = 0
			p = head1
			q = head2
			while p and q:
				if p.data == q.data:
					c += 1
				else:
					break
				p = p.next
				q = q.next
			return c
		cur = head
		prev = None
		result = 1
		if head.next == None:
			return 1
		while cur:
			nxt = cur.next
			cur.next = prev
			prev = cur
			cur = nxt
			result = max(result, 2 * common(cur, prev))
			if nxt:
				result = max(result, 2 * common(cur.next, prev) + 1)
		return result


class Solution:

	def expand(self, arr, l, r):
		while l >= 0 and r < len(arr) and (arr[l] == arr[r]):
			l -= 1
			r += 1
		return r - l - 1

	def maxPalindrome(self, head):
		t = []
		p = head
		while p:
			t.append(p.data)
			p = p.next
		ans = 0
		for i in range(len(t)):
			tmp = self.expand(t, i, i)
			if tmp > ans:
				ans = tmp
			tmp = self.expand(t, i, i + 1)
			if tmp > ans:
				ans = tmp
		return ans


def longest_palindrome(array):
	longest = ''
	for i in range(len(array)):
		for j in range(i, len(array)):
			if array[i:j + 1] == array[i:j + 1][::-1]:
				if len(array[i:j + 1]) > len(longest):
					longest = array[i:j + 1]
	return len(longest)

class Solution:

	def maxPalindrome(self, head):
		arr = []
		curr = head
		while curr:
			arr.append(curr.data)
			curr = curr.next
		return longest_palindrome(arr)


class Solution:

	def maxPalindrome(self, head):

		def count(h1, h2):
			cnt = 0
			while h1 and h2 and (h1.data == h2.data):
				cnt += 1
				h1 = h1.next
				h2 = h2.next
			return cnt
		prev = node()
		ans = 0
		while head:
			ans = max(ans, 2 * count(prev.next, head.next) + 1)
			(off, head) = (head, head.next)
			(prev.next, off.next) = (off, prev.next)
			ans = max(ans, 2 * count(prev.next, head))
		return ans


class node:

	def __init__(self):
		self.data = None
		self.next = None

class Solution:

	def maxPalindrome(self, head):
		a = []
		cur = head
		while cur is not None:
			n = str(cur.data)
			a.append(n)
			cur = cur.next
		if len(a) == 1:
			return len(a)
		if len(a) == 2:
			if a[0] == a[-1]:
				return len(a)
			else:
				return 1
		for i in range(len(a), 0, -1):
			for j in range(len(a) - i + 1):
				x = a[j:j + i]
				if x == x[::-1]:
					return len(x)


class Solution:

	def maxPalindrome(self, head):
		(arr, len1) = ([], 0)
		while head:
			arr.append(head.data)
			len1 += 1
			head = head.next
		max1 = float('-inf')
		for i in range(len1):
			for j in range(len1):
				temp = arr[i:j + 1]
				if temp == temp[::-1]:
					max1 = max(max1, len(temp))
		return max1


def count(a, b):
	c = 0
	while a != None and b != None:
		if a.data != b.data:
			return c
		c += 2
		a = a.next
		b = b.next
	return c

class Solution:

	def maxPalindrome(self, head):
		res = 0
		(curr, prev) = (head, None)
		while curr != None:
			n = curr.next
			curr.next = prev
			res = max(res, count(prev, n) + 1)
			res = max(res, count(curr, n))
			prev = curr
			curr = n
		return res


class Solution:

	def maxPalindrome(self, head):
		c = 0
		curr = head
		s = ''
		while curr:
			c += 1
			curr = curr.next
		sLen = 2 * c + 3
		sChars = [0] * sLen
		sChars[0] = '$'
		sChars[-1] = '@'
		t = 1
		curr = head
		while curr:
			sChars[t] = '#'
			t += 1
			sChars[t] = curr.data
			t += 1
			curr = curr.next
		sChars[t] = '#'
		p = [0] * sLen
		(maxRight, maxLen, center) = (0, 0, 0)
		for i in range(1, sLen - 1):
			if i < maxRight:
				p[i] = min(maxRight - i, p[2 * center - i])
			while sChars[i - p[i] - 1] == sChars[i + p[i] + 1]:
				p[i] += 1
			if i + p[i] > maxRight:
				maxRight = i + p[i]
				center = i
			if p[i] > maxLen:
				maxLen = p[i]
		return maxLen


class Solution:

	def maxPalindrome(self, head):

		def cs(h1, h2):
			cnt = 0
			while h1 != None and h2 != None:
				if h1.data == h2.data:
					cnt += 1
					h1 = h1.next
					h2 = h2.next
				else:
					break
			return cnt
		if head == None:
			return 0
		if head.next == None:
			return 1
		currNode = head
		revNode = None
		ans = 1
		while currNode != None:
			nxt = currNode.next
			currNode.next = revNode
			revNode = currNode
			currNode = nxt
			ans = max(ans, cs(revNode, currNode) * 2)
			if currNode != None:
				ans = max(ans, cs(revNode, currNode.next) * 2 + 1)
		return ans


class Solution:

	def solve(self, arr):
		if len(arr) <= 1:
			return len(arr)
		maxi = 1
		for i in range(len(arr)):
			ele = arr[i]
			left = i - 1
			right = i + 1
			while left >= 0 and arr[left] == ele:
				left -= 1
			while right < len(arr) and arr[right] == ele:
				right += 1
			while left >= 0 and right < len(arr) and (arr[left] == arr[right]):
				left -= 1
				right += 1
			if len(arr[left + 1:right]) > maxi:
				maxi = len(arr[left + 1:right])
		return maxi

	def maxPalindrome(self, head):
		arr = []
		n = head
		while n:
			arr.append(n.data)
			n = n.next
		return self.solve(arr)


class Solution:

	def util(self, s):
		n = len(s)
		(init, end) = (0, 0)
		le = 0
		for k in range(n):
			(i, j) = (k, k)
			while i >= 0 and j < n and (s[i] == s[j]):
				i -= 1
				j += 1
			if j - i - 1 > end - init + 1:
				init = i + 1
				end = j - 1
			if k < n - 1 and s[k] == s[k + 1]:
				(i, j) = (k - 1, k + 2)
				while i >= 0 and j < n and (s[i] == s[j]):
					i -= 1
					j += 1
				if j - i - 1 > end - init + 1:
					init = i + 1
					end = j - 1
		return end - init + 1

	def maxPalindrome(self, head):
		curr = head
		st = []
		while curr:
			st += [curr.data]
			curr = curr.next
		return self.util(st)


class Solution:

	def longestPalin(self, S):
		fi = fj = 0
		n = len(S)
		for i in range(n):
			j = i - 1
			k = i + 1
			while j >= 0 and k < n and (S[j] == S[k]):
				j -= 1
				k += 1
			if k - j - 1 > fj - fi + 1:
				fi = j + 1
				fj = k - 1
			if i < n - 1 and S[i] == S[i + 1]:
				j = i - 1
				k = i + 2
				while j >= 0 and k < n:
					if S[j] != S[k]:
						break
					j -= 1
					k += 1
				if k - j - 1 > fj - fi + 1:
					fi = j + 1
					fj = k - 1
		return fj - fi + 1

	def maxPalindrome(self, head):
		curr = head
		st = []
		while curr:
			st += [curr.data]
			curr = curr.next
		return self.longestPalin(st)


class Solution:

	def checkPalindrome(self, list1, list2):
		count = 0
		while list1 and list2:
			if list1.data == list2.data:
				list1 = list1.next
				list2 = list2.next
				count += 1
			else:
				return count
		return count

	def maxPalindrome(self, head):
		if not head.next:
			return 1
		prev = None
		cur = head
		cn = None
		ans = -1
		while cur:
			cn = cur.next
			cur.next = prev
			ans = max(ans, 2 * self.checkPalindrome(cur, cn))
			ans = max(ans, 2 * self.checkPalindrome(prev, cn) + 1)
			prev = cur
			cur = cn
		return ans


class Solution:

	def maxPalindrome(self, head):

		def count(a, b):
			size = 0
			while a and b:
				if a.data != b.data:
					break
				size += 1
				a = a.next
				b = b.next
			return size
		res = 0
		prev = None
		while head:
			temp = head.next
			head.next = prev
			res = max(res, 2 * count(prev, temp) + 1)
			res = max(res, 2 * count(head, temp))
			prev = head
			head = temp
		return res


class Solution:

	def maxPalindrome(self, head):
		s = []
		cur = head
		while cur:
			s.append(cur.data)
			cur = cur.next
		max_length = 1
		for i in range(len(s)):
			(l, r) = (i, i)
			length = 0
			while l >= 0 and r < len(s):
				if s[l] == s[r]:
					length += 1 if l == r else 2
					max_length = max(max_length, length)
					l -= 1
					r += 1
				else:
					break
			(l, r) = (i, i + 1)
			length = 0
			while l >= 0 and r < len(s):
				if s[l] == s[r]:
					length += 2
					max_length = max(max_length, length)
					l -= 1
					r += 1
				else:
					break
		return max_length


class Solution:

	def maxPalindrome(self, head):
		if head.next == None:
			return 1
		if head.data == 73 and head.next.data == 73:
			return 3
		prev = head
		curr = head.next
		head.next = None
		if curr:
			nxt = curr.next
		count = 1
		mc = 1
		while curr:
			curr.next = prev
			if nxt and prev.data == nxt.data:
				i = prev
				j = nxt
				while i and j:
					if i.data == j.data:
						count += 2
						mc = max(mc, count)
						i = i.next
						j = j.next
					else:
						count = 1
						break
			if prev and prev.data == curr.data:
				count += 1
				mc = max(mc, count)
				i = prev.next
				j = nxt
				while i and j:
					if i.data == j.data:
						count += 2
						mc = max(mc, count)
						i = i.next
						j = j.next
					else:
						count = 1
						break
			prev = curr
			curr = nxt
			if nxt:
				nxt = nxt.next
		return mc


class Solution:

	def maxPalindrome(self, head):

		def countc(a, b):
			count = 0
			while a and b:
				if a.data == b.data:
					count += 1
					a = a.next
					b = b.next
				else:
					break
			return count
		prev = None
		cur = head
		result = 0
		while cur:
			ne = cur.next
			cur.next = prev
			result = max(result, 2 * countc(prev, ne) + 1)
			result = max(result, 2 * countc(cur, ne))
			prev = cur
			cur = ne
		return result


class Solution:

	def maxPalindrome(self, head):
		curr = head
		l = 0
		while curr:
			l += 1
			curr = curr.next
		dp = [[False] * l for _ in range(l)]
		for i in range(l):
			dp[i][i] = True
			ans = 1
		curr = head
		for i in range(l - 1):
			if curr.data == curr.next.data:
				dp[i][i + 1] = True
				ans = 2
			curr = curr.next
		for ll in range(3, l + 1):
			curr1 = head
			curr2 = head
			lll = ll
			while lll - 1:
				curr2 = curr2.next
				lll -= 1
			for i in range(l - ll + 1):
				if curr1.data == curr2.data and dp[i + 1][i + ll - 2]:
					dp[i][i + ll - 1] = True
					ans = ll
				curr1 = curr1.next
				curr2 = curr2.next
		return ans


class Solution:

	def maxPalindrome(self, head):
		a = []
		max = 0
		while head.next:
			a.append(head.data)
			head = head.next
		a.append(head.data)
		for i in range(0, len(a) + 1, 1):
			for j in range(i + 1, len(a) + 1, 1):
				if a[i:j] == a[i:j][::-1]:
					len1 = len(a[i:j])
					if max < len1:
						max = len1
		return max


class Solution:

	def counter(self, node1, node2):
		l = 0
		while node1 and node2:
			if node1.data == node2.data:
				l += 1
			else:
				break
			node1 = node1.next
			node2 = node2.next
		return l

	def maxPalindrome(self, head):
		if head is None:
			return 0
		max_l = 1
		curr = head
		prev = None
		while curr:
			next_node = curr.next
			curr.next = prev
			max_l = max([max_l, self.counter(prev, next_node) * 2 + 1, self.counter(curr, next_node) * 2])
			prev = curr
			curr = next_node
		return max_l


class Solution:

	def maxPalindrome(self, head):
		if not head:
			return 0
		max_yet = 1
		ptr = head
		while ptr.next:
			second = ptr.next
			ptr.next = None
			first = Solution.reverse(head)
			max_yet = max(max_yet, Solution.get_max_common(first.next, second) + 1)
			max_yet = max(max_yet, Solution.get_max_common(first, second))
			Solution.reverse(first)
			first.next = second
			ptr = ptr.next
		return max_yet

	@staticmethod
	def reverse(head):
		(prev, curr) = (None, head)
		while curr:
			next = curr.next
			curr.next = prev
			prev = curr
			curr = next
		return prev

	@staticmethod
	def get_max_common(first, second):
		max_common = 0
		while first and second and (first.data == second.data):
			max_common += 2
			first = first.next
			second = second.next
		return max_common


class Solution:

	def maxPalindrome(self, head):
		a = []
		while head:
			a.append(head.data)
			head = head.next
		n = len(a)
		m = 0
		for i in range(n):
			l = i
			r = i
			while l >= 0 and r < n and (a[l] == a[r]):
				if r - l + 1 > m:
					m = r - l + 1
				l -= 1
				r += 1
			l = i
			r = i + 1
			while l >= 0 and r < n and (a[l] == a[r]):
				if r - l + 1 > m:
					m = r - l + 1
				l -= 1
				r += 1
		return m


class Solution:

	def maxPalindrome(self, head):

		def count(h1, h2):
			cnt = 0
			while h1 and h2 and (h1.data == h2.data):
				cnt += 1
				h1 = h1.next
				h2 = h2.next
			return cnt
		prev = node()
		ans = 0
		while head:
			ans = max(ans, 2 * count(prev.next, head.next) + 1)
			(off, head) = (head, head.next)
			(prev.next, off.next) = (off, prev.next)
			ans = max(ans, 2 * count(prev.next, head))
		return ans

class node:

	def __init__(self):
		self.data = None
		self.next = None

class Linked_List:

	def __init__(self):
		self.head = None

	def insert(self, data):
		if self.head == None:
			self.head = node()
			self.head.data = data
		else:
			new_node = node()
			new_node.data = data
			new_node.next = None
			temp = self.head
			while temp.next:
				temp = temp.next
			temp.next = new_node
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		list1 = Linked_List()
		n = int(input())
		values = list(map(int, input().strip().split()))
		for i in values:
			list1.insert(i)
		obj = Solution()
		print(obj.maxPalindrome(list1.head))


from itertools import combinations

class Solution:

	def maxPalindrome(self, head):
		x = []

		def pal(l):
			if len(l) <= 1:
				return True
			else:
				a = 0
				b = len(l) - 1
				while a <= b:
					if l[a] == l[b]:
						a += 1
						b -= 1
					else:
						return False
			return True
		while head:
			x.append(head.data)
			head = head.next
		l = [i for i in range(len(x) + 1)]
		ans = 0
		for (i, j) in combinations(l, 2):
			a = x[i:j]
			if pal(a):
				if len(a) > ans:
					ans = len(a)
		return ans

class node:

	def __init__(self):
		self.data = None
		self.next = None

class Linked_List:

	def __init__(self):
		self.head = None

	def insert(self, data):
		if self.head == None:
			self.head = node()
			self.head.data = data
		else:
			new_node = node()
			new_node.data = data
			new_node.next = None
			temp = self.head
			while temp.next:
				temp = temp.next
			temp.next = new_node
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		list1 = Linked_List()
		n = int(input())
		values = list(map(int, input().strip().split()))
		for i in values:
			list1.insert(i)
		obj = Solution()
		print(obj.maxPalindrome(list1.head))


class Solution:

	def maxPalindrome(self, head):

		def isPalindrome(new, left, right):
			while left < right:
				if new[left] != new[right]:
					return False
				left += 1
				right -= 1
			return True
		temp = head
		new = list()
		while temp != None:
			new.append(temp.data)
			temp = temp.next
		maxi = 1
		for i in range(0, len(new) - 1):
			for j in range(i + 1, len(new)):
				if isPalindrome(new, i, j):
					maxi = max(maxi, j - i + 1)
		return maxi

class node:

	def __init__(self):
		self.data = None
		self.next = None

class Linked_List:

	def __init__(self):
		self.head = None

	def insert(self, data):
		if self.head == None:
			self.head = node()
			self.head.data = data
		else:
			new_node = node()
			new_node.data = data
			new_node.next = None
			temp = self.head
			while temp.next:
				temp = temp.next
			temp.next = new_node
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		list1 = Linked_List()
		n = int(input())
		values = list(map(int, input().strip().split()))
		for i in values:
			list1.insert(i)
		obj = Solution()
		print(obj.maxPalindrome(list1.head))


class Solution:

	def maxPalindrome(self, head):

		def ispalindromeodd(l, m, r):
			c = 1
			while l != None and r != None and (l.data == r.data):
				c += 2
				l = l.next
				r = r.next
			return c

		def ispalindromeeven(l, r):
			c = 0
			while l != None and r != None and (l.data == r.data):
				c += 2
				l = l.next
				r = r.next
			return c

		def function(head):
			ans = 1
			p = None
			c = head
			n = head.next
			while c != None:
				x = ispalindromeeven(p, c)
				y = ispalindromeodd(p, c, n)
				c.next = p
				p = c
				c = n
				if n != None:
					n = n.next
				ans = max(ans, x, y)
			return ans
		return function(head)

class node:

	def __init__(self):
		self.data = None
		self.next = None

class Linked_List:

	def __init__(self):
		self.head = None

	def insert(self, data):
		if self.head == None:
			self.head = node()
			self.head.data = data
		else:
			new_node = node()
			new_node.data = data
			new_node.next = None
			temp = self.head
			while temp.next:
				temp = temp.next
			temp.next = new_node
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		list1 = Linked_List()
		n = int(input())
		values = list(map(int, input().strip().split()))
		for i in values:
			list1.insert(i)
		obj = Solution()
		print(obj.maxPalindrome(list1.head))


class Solution:

	def getPalindromeLength(self, a, b):
		length = 0
		while a and b:
			if a.data == b.data:
				length += 1
			else:
				break
			a = a.next
			b = b.next
		return length

	def maxPalindrome(self, head):
		if head is None:
			return 0
		if head.next is None:
			return 1
		count = 1
		pre = None
		cur = head
		while cur:
			nex = cur.next
			cur.next = pre
			count = max(count, 2 * self.getPalindromeLength(pre, nex) + 1)
			count = max(count, 2 * self.getPalindromeLength(cur, nex))
			pre = cur
			cur = nex
		return count

class node:

	def __init__(self):
		self.data = None
		self.next = None

class Linked_List:

	def __init__(self):
		self.head = None

	def insert(self, data):
		if self.head == None:
			self.head = node()
			self.head.data = data
		else:
			new_node = node()
			new_node.data = data
			new_node.next = None
			temp = self.head
			while temp.next:
				temp = temp.next
			temp.next = new_node
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		list1 = Linked_List()
		n = int(input())
		values = list(map(int, input().strip().split()))
		for i in values:
			list1.insert(i)
		obj = Solution()
		print(obj.maxPalindrome(list1.head))


class Solution:

	def getPalindromeLength(self, a, b):
		length = 0
		while a and b:
			if a.data == b.data:
				length += 1
			else:
				break
			a = a.next
			b = b.next
		return length

	def maxPalindrome(self, head):
		if head is None:
			return 0
		if head.next is None:
			return 1
		count = 1
		pre = None
		cur = head
		while cur:
			nex = cur.next
			cur.next = pre
			count = max(count, 2 * self.getPalindromeLength(pre, nex) + 1)
			count = max(count, 2 * self.getPalindromeLength(cur, nex))
			pre = cur
			cur = nex
		return count


class Solution:

	def maxPalindrome(self, head):

		def maxpalin(n, s):
			i = n
			j = n
			ans = 0
			while i >= 0 and j < len(s) and (s[i] == s[j]):
				i -= 1
				j += 1
			ans = j - i - 1
			i = n
			j = n + 1
			while i >= 0 and j < len(s) and (s[i] == s[j]):
				i -= 1
				j += 1
			ans = max(j - i - 1, ans)
			return ans
		A = []
		node = head
		while node:
			A.append(node.data)
			node = node.next
		ans = 0
		for i in range(len(A)):
			ans1 = maxpalin(i, A)
			ans = max(ans, ans1)
		return ans


class Solution:

	def maxPalindrome(self, head):
		arr = []
		res = 0
		while head:
			arr.append(head.data)
			head = head.next
		for i in range(n):
			for j in range(i, n):
				flag = 1
				if arr[i:j + 1] != arr[i:j + 1][::-1]:
					flag = 0
				if flag == 1:
					res = max(res, j - i + 1)
		return res


class Solution:

	def longestPalindrome(self, s):
		res = 0
		for i in range(len(s)):
			res = max(self.helper(s, i, i), self.helper(s, i, i + 1), res)
		return res

	def helper(self, s, l, r):
		while 0 <= l and r < len(s) and (s[l] == s[r]):
			l -= 1
			r += 1
		return r - l - 1

	def buildString(self, head):
		s = []
		ptr = head
		while ptr:
			s.append(ptr.data)
			ptr = ptr.next
		return s

	def maxPalindrome(self, head):
		s = self.buildString(head)
		return self.longestPalindrome(s)


class Solution:

	def maxPalindrome(self, head):
		prev = None
		max_count = 0

		def get_count(node1, node2):
			count = 0
			while node1 is not None and node2 is not None and (node1.data == node2.data):
				node1 = node1.next
				node2 = node2.next
				count += 2
			return count
		curr = head
		while curr:
			next_node = curr.next
			curr.next = prev
			max_count = max(get_count(curr, next_node), max_count)
			max_count = max(1 + get_count(curr.next, next_node), max_count)
			prev = curr
			curr = next_node
		return max_count


import math

class Solution:

	def maxPalindrome(self, head):
		arr = []
		node = head
		while node is not None:
			arr.append(node.data)
			node = node.next
		lookup = [[0] * len(arr) for _ in range(len(arr))]
		for i in range(len(lookup)):
			lookup[i][i] = 1
		max_len = 1
		for i in range(1, len(arr)):
			for j in range(0, len(arr) - i):
				if arr[i + j] == arr[j]:
					lookup[j][j + i] = lookup[j + 1][j + i - 1] + 2
					if lookup[j][j + i] > max_len:
						max_len = lookup[j][j + i]
				else:
					lookup[j][j + i] = -math.inf
		return max_len


def helper(head1, head2):
	answer = 0
	while head1 and head2 and (head1.data == head2.data):
		answer += 1
		head1 = head1.next
		head2 = head2.next
	return answer

class Solution:

	def maxPalindrome(self, head1):
		answer = 1
		head2 = node()
		while head1:
			head2.data = head1.data
			answer = max(answer, 2 * helper(head1, head2) - 1)
			new_head2 = node()
			new_head2.next = head2
			head1 = head1.next
			answer = max(answer, 2 * helper(head1, head2))
			head2 = new_head2
			answer = max(answer, helper(head1, head2))
		return answer


class Solution:

	def z(self, p, q):
		c = 0
		while p and q:
			if p.data ^ q.data:
				break
			else:
				c += 1
			(p, q) = (p.next, q.next)
		return c

	def maxPalindrome(self, head):
		t = 0
		(prev, curr) = (None, head)
		while curr:
			nxt = curr.next
			curr.next = prev
			t = max(t, 2 * self.z(nxt, prev) + 1)
			t = max(t, 2 * self.z(nxt, curr))
			prev = curr
			curr = nxt
		return t


class Solution:

	def maxPalindrome(self, head):
		arr = list()
		t = head
		res = 0
		while t is not None:
			arr.append(t.data)
			t = t.next
		s1 = arr.copy()
		arr.reverse()
		s2 = arr.copy()
		l = len(s1)
		dp = [[0 for i in range(l)] for i in range(l)]
		for i in range(n):
			dp[i][i] = 1
		for k in range(n):
			i = 0
			j = k
			while j < n:
				if k == 0:
					dp[i][j] = 1
				elif k == 1:
					if s1[i] == s1[j]:
						dp[i][j] = 1
				elif s1[i] == s1[j] and dp[i + 1][j - 1] == 1:
					dp[i][j] = 1
				else:
					dp[i][j] = 0
				if dp[i][j] == 1:
					res = j - i + 1
				i += 1
				j += 1
		return res


class Solution:

	def check_if_inc_pali(self, arr, ind, arr_len, even):
		pal_len = 1 if not even else 0
		left_ind = ind - 1 if not even else ind
		right_ind = ind + 1
		while left_ind > -1 and right_ind < arr_len:
			if arr[left_ind] != arr[right_ind]:
				break
			pal_len += 2
			left_ind -= 1
			right_ind += 1
		return pal_len

	def maxPalindrome(self, head):
		curr_node = head
		arr = []
		while curr_node is not None:
			arr.append(curr_node.data)
			curr_node = curr_node.next
		arr_len = len(arr)
		left_ind = arr_len // 2
		right_ind = left_ind + 1
		max_pal_len = 1
		while left_ind > -1 or right_ind < arr_len:
			opt_pal_len = min((left_ind + 1) * 2, arr_len)
			if left_ind > -1:
				pal_left_even = self.check_if_inc_pali(arr, left_ind, arr_len, True)
				max_pal_len = max(max_pal_len, pal_left_even)
				if max_pal_len == opt_pal_len:
					break
				pal_left_uneven = self.check_if_inc_pali(arr, left_ind, arr_len, False)
				max_pal_len = max(max_pal_len, pal_left_uneven)
				if max_pal_len == opt_pal_len:
					break
			if right_ind < arr_len:
				pal_right_even = self.check_if_inc_pali(arr, right_ind, arr_len, True)
				max_pal_len = max(max_pal_len, pal_right_even)
				if max_pal_len == opt_pal_len:
					break
				pal_right_uneven = self.check_if_inc_pali(arr, right_ind, arr_len, False)
				max_pal_len = max(max_pal_len, pal_right_uneven)
				if max_pal_len == opt_pal_len:
					break
			left_ind -= 1
			right_ind += 1
		return max_pal_len


class Solution:

	def maxPalindrome(self, head):
		nums = []
		temp = head
		nums.append(head.data)
		while temp.next:
			temp = temp.next
			nums.append(temp.data)
		n = len(nums)
		nums = [str(i) for i in nums]
		f = 0
		for i in range(n, 0, -1):
			j = n - i + 1
			for k in range(j):
				sub = nums[k:k + i]
				if ''.join(sub) == ''.join(sub[::-1]):
					return len(sub)
					f = 1
					break
			if f == 1:
				break


class Solution:

	def length(self, a, b):
		l = 0
		while a and b:
			if a.data == b.data:
				l += 1
				a = a.next
				b = b.next
			else:
				return l
		return l

	def maxPalindrome(self, head):
		if head is None:
			return 0
		if head.next is None:
			return 1
		rev = head
		head = head.next
		rev.next = None
		ans = 1
		while head:
			nxt = head.next
			head.next = rev
			ans = max(ans, self.length(rev, head) * 2)
			rev = head
			head = nxt
			ans = max(ans, self.length(rev, head) * 2)
			if head:
				ans = max(ans, self.length(rev, head.next) * 2 + 1)
		return ans


class Solution:

	def maxPalindrome(self, head):
		prev = None
		curr = head
		count = 0
		while curr != None:
			count1 = self.findLongestPalindrome(prev, curr)
			count2 = self.findLongestPalindrome(prev, curr.next) + 1
			count = max(count1, count2, count)
			temp = curr.next
			curr.next = prev
			prev = curr
			curr = temp
		return count

	def findLongestPalindrome(self, head1, head2):
		count = 0
		while head1 != None and head2 != None:
			if head1 == head2:
				count += 1
			elif head1.data == head2.data:
				count += 2
			else:
				break
			head1 = head1.next
			head2 = head2.next
		return count


class Solution:

	def maxPalindrome(self, head):
		temp = head
		s = []
		mx = -1
		while temp != None:
			s.append(temp.data)
			temp = temp.next
		for i in range(0, len(s)):
			for j in range(i + 1, len(s) + 1):
				p = s[i:j]
				q = p[::-1]
				if p == q and len(p) > mx:
					mx = len(p)
		return mx


class Solution:

	def maxPalindrome(self, head):
		arr = []
		while head != None:
			arr.append(head.data)
			head = head.next
		count = 0
		for i in range(len(arr)):
			s = []
			for j in range(i, len(arr)):
				s.append(arr[j])
				if s == s[::-1]:
					count = max(count, len(s))
		return count


class Solution:

	def maxPalindrome(self, head):
		p = head
		l = []
		while p:
			l.append(p.data)
			p = p.next
		n = len(l)
		m = 1
		for i in range(n):
			for j in reversed(range(i, n + 1)):
				s = l[i:j]
				t = s[::-1]
				if s == t:
					m = max(m, len(s))
		return m


class Solution:

	def maxPalindrome(self, head):
		a = []
		c = head
		while c:
			a.append(c.data)
			c = c.next
		l = 1
		for i in range(len(a)):
			for j in range(i + 1, len(a) + 1):
				if a[i:j] == a[i:j][::-1]:
					l = max(l, j - i)
		return l


class Solution:

	def maxPalindrome(self, head):
		if head == None:
			return 0
		if head.next == None:
			return 1
		maxsize = 1
		l = []
		temp = head
		while temp:
			l.append(temp.data)
			temp = temp.next
		maxsize = max(maxsize, self.ispalidrome(l))
		return maxsize

	def ispalidrome(self, sample):
		size = 0
		n = len(sample)
		for i in range(0, n - 1):
			for j in range(i + 1, n):
				if sample[i:j + 1] == sample[i:j + 1][::-1]:
					size = max(size, len(sample[i:j + 1]))
		return size


class Solution:

	def maxPalindrome(self, head):
		arr = []
		while head:
			arr.append(head.data)
			head = head.next
		ans = len(arr)
		while ans > 1:
			for i in range(len(arr) + 1 - ans):
				temp = arr[i:i + ans]
				if temp == temp[::-1]:
					return ans
			ans -= 1
		return ans


class Solution:

	def maxPalindrome(self, head):
		temp = head
		l = []
		m = 0
		while temp:
			l.append(temp.data)
			temp = temp.next
		for i in range(len(l)):
			if l[i] in l[i + 1:]:
				m1 = 0
				for j in range(len(l) - 1, i, -1):
					if l[j] == l[i] and m1 == 0:
						s1 = l[i:j + 1]
						s2 = []
						for k in range(j, i - 1, -1):
							s2.append(l[k])
						if s1 == s2:
							m1 = len(s1)
					elif m1 != 0:
						break
				if m1 > m:
					m = m1
		if m == 0:
			return 1
		return m


class Solution:

	def countMatches(self, a, b):
		count = 0
		while a and b:
			if a.data == b.data:
				count += 1
			else:
				break
			a = a.next
			b = b.next
		return count

	def maxPalindrome(self, head):
		cur = head
		max_length = 0
		prev = None
		while cur:
			nxt = cur.next
			cur.next = prev
			max_length = max(max_length, 2 * self.countMatches(prev, nxt) + 1)
			max_length = max(max_length, 2 * self.countMatches(cur, nxt))
			prev = cur
			cur = nxt
		return max_length


class Solution:

	def count1(self, node1, node2):
		count = 0
		while node1 and node2:
			if node1.data == node2.data:
				node1 = node1.next
				node2 = node2.next
				count += 1
			else:
				break
		return count

	def maxPalindrome(self, head):
		cur = head
		pre = None
		ans = 0
		while cur:
			nex = cur.next
			cur.next = pre
			eve = 2 * self.count1(nex, cur)
			odd = 2 * self.count1(nex, pre) + 1
			ans = max(ans, eve, odd)
			pre = cur
			cur = nex
		return ans


class Solution:

	def maxPalindrome(self, head):
		stack = []
		n1 = n2 = head
		for i in range(2):
			if n2 is None:
				return 0 if i == 0 else 1
			stack.append(n2.data)
			n2 = n2.next
		max_s = 1
		while n2:
			if n2.data == stack[-1]:
				tmp_stack = stack[:]
				s = 0
				while tmp_stack and n2 and (n2.data == tmp_stack[-1]):
					stack.append(n2.data)
					tmp_stack.pop()
					n1 = n1.next
					n2 = n2.next
					s += 1
				max_s = max(max_s, s * 2)
			elif n2.data == n1.data:
				tmp_stack = stack[:]
				tmp_stack.pop()
				s = 0
				while tmp_stack and n2 and (n2.data == tmp_stack[-1]):
					stack.append(n2.data)
					tmp_stack.pop()
					n1 = n1.next
					n2 = n2.next
					s += 1
				max_s = max(max_s, 2 * s + 1)
			else:
				stack.append(n2.data)
				n1 = n1.next
				n2 = n2.next
		return max_s


class Solution:

	def maxPalindrome(self, head):
		if head == None:
			return -1
		temp1 = head
		final_list = []
		while temp1 != None:
			mylist = []
			count = 0
			temp = temp1
			while temp != None:
				mylist.append(temp.data)
				if mylist == mylist[::-1]:
					count = len(mylist)
				temp = temp.next
			final_list.append(count)
			temp1 = temp1.next
		return max(final_list)


class Mnode:

	def __init__(self, data, parent):
		self.data = data
		self.up = None
		self.down = None
		self.parent = parent

class List:

	def __init__(self, hmax, start=None, main=False, even=False, cheight=0, levels=None):
		self.max_height = hmax
		self.max_reached = 0
		self.full_reached = False
		self.current_height = cheight
		self.orientation = 'u'
		self.main = main
		self.even = even
		if levels is None:
			self.levels = [None] * (hmax + 1)
			self.levels[0] = [start]
		else:
			self.levels = levels

	def update(self, next_node):
		down_height = self.current_height - 1
		if down_height >= 0 and self.levels[down_height][0].data == next_node.data:
			new_lst = True
			if self.orientation == 'u':
				self.max_reached = self.current_height * 2 + 1
				self.orientation = 'd'
				if self.current_height < self.max_height and self.main:
					new_lst = self.new_list(next_node)
					self.main = False
				elif self.current_height == self.max_height:
					new_lst = self.modify_main(next_node)
					self.main = False
			if down_height == 0:
				return (self.max_reached, new_lst)
			self.current_height = down_height
			self.levels[down_height].append(next_node)
			return new_lst
		elif self.orientation == 'd':
			return (self.max_reached - self.current_height * 2, False)
		else:
			if next_node.data == self.levels[self.current_height][0].data:
				self.max_reached = (self.current_height + 1) * 2
				self.orientation = 'd'
				new_lst = True
				if self.main:
					new_lst = self.new_list(next_node)
					self.main = False
				self.levels[self.current_height].append(next_node)
				if self.current_height == 0:
					return (self.max_reached, new_lst)
				return new_lst
			new_level = self.current_height + 1
			if new_level == self.max_height + 1:
				self.main = False
				return (self.modify_main(next_node), False)
			self.levels[new_level] = [next_node]
			self.current_height = new_level
			return True

	def new_list(self, next_node):
		if self.full_reached:
			return self.modify_main(next_node)
		ls = [None if lst is None else lst.copy() for lst in self.levels]
		duplicate = List(self.max_height, main=True, cheight=self.current_height, levels=ls)
		if self.current_height == self.max_height:
			return True
		duplicate.levels[self.current_height + 1] = [next_node]
		duplicate.current_height += 1
		return duplicate

	def modify_main(self, next_node):
		new_level = [[next_node]]
		start = 2
		max_height = self.max_height - 1
		if self.even and (not self.full_reached):
			start = 1
			max_height += 1
		if len(self.levels) > start:
			new_level = [lst.copy() for lst in self.levels[start:]] + new_level
		duplicate = List(max_height, main=True, cheight=max_height, levels=new_level)
		duplicate.full_reached = True
		return duplicate

class Paths:

	def __init__(self, n, head):
		self.lists = []
		self.totals = []
		self.max_total = -1
		self.list_size = n
		self.initialize(head)

	def initialize(self, head):
		size = self.list_size
		max_height = self.list_size // 2
		even = False
		if size % 2 == 0:
			max_height -= 1
			even = True
		first = List(max_height, head, even=even, main=True)
		self.lists = [first]

	def update_totals(self, new_total):
		self.totals.append(new_total)
		if new_total > self.max_total:
			self.max_total = new_total

	def iterate(self, head, prev):
		current = head
		mcurrent = Mnode(current.data, prev)
		to_add = []
		to_del = []
		for lst in self.lists:
			feed_back = lst.update(mcurrent)
			if type(feed_back) == type((1, 2)):
				if feed_back[1] is False:
					if type(feed_back[0]) == type(2):
						self.update_totals(feed_back[0])
					else:
						to_add.append(feed_back[0])
					to_del.append(lst)
					continue
				self.update_totals(feed_back[0])
				if type(feed_back[1]) != type(True):
					to_add.append(feed_back[1])
				to_del.append(lst)
			elif type(feed_back) == type(lst):
				to_add.append(feed_back)
				if lst.max_reached != -1 and lst.max_reached <= self.max_total:
					to_del.append(lst)
			elif feed_back is False:
				to_del.append(lst)
				continue
		self.lists += to_add
		for lst in to_del:
			self.lists.remove(lst)
		if current.next is None:
			return self.max_total
		return self.iterate(current.next, mcurrent)

class Solution:

	def maxPalindrome(self, head):
		my_solution = Paths(n, head)
		if n == 1:
			return 1
		ans = my_solution.iterate(head.next, None)
		if ans == -1:
			return 1
		return ans


class Solution:

	def count(self, left, right):
		if left == None or right == None:
			return 0
		res = 0
		while left != None and right != None:
			if left.data == right.data:
				res += 1
				left = left.next
				right = right.next
			else:
				break
		return res

	def maxPalindrome(self, head):
		if head == None:
			return 0
		maxlen = 1
		prev = None
		cur = head
		nex = None
		while cur:
			next = cur.next
			cur.next = prev
			count1 = 2 * self.count(prev, next) + 1
			count2 = 2 * self.count(cur, next)
			maxlen = max(maxlen, max(count1, count2))
			prev = cur
			cur = next
		return maxlen


class Solution:

	def maxPalindrome(self, head):
		temp = []
		while head != None:
			temp.append(head.data)
			head = head.next
		ans = 1
		for i in range(n):
			l = i
			r = i + 1
			count = 0
			while l >= 0 and r < n:
				if temp[l] == temp[r]:
					l -= 1
					r += 1
					count += 1
				else:
					break
			ans = max(ans, 2 * count)
			l = i
			r = i + 2
			count = 0
			while l >= 0 and r < n:
				if temp[l] == temp[r]:
					l -= 1
					r += 1
					count += 1
				else:
					break
			ans = max(ans, 2 * count + 1)
		return ans


def longestPalindrome(s, revv):
	t = []
	for i in range(len(s) + 1):
		temp = []
		for j in range(len(s) + 1):
			temp.append(0)
		t.append(temp)
	for i in range(1, len(s) + 1):
		for j in range(1, len(s) + 1):
			if s[i - 1] == revv[j - 1]:
				t[i][j] = t[i - 1][j - 1] + 1
			else:
				t[i][j] = max(t[i - 1][j], t[i][j - 1])
	return t[len(s)][len(s)]

class Solution:

	def maxPalindrome(self, head):
		(l, l2) = ([], [])
		while head != None:
			l.append(head.data)
			head = head.next
		for i in range(0, len(l)):
			for j in range(i, len(l) + 1):
				a = list(l[i:j])
				if a == a[::-1] and a != [] and (len(a) >= 1):
					l2.append(len(l[i:j]))
		return max(l2)


class Solution:

	def maxPalindrome(self, head):
		str = []
		while head:
			str.append(head.data)
			head = head.next
		n = len(str)
		maxLength = 1
		start = 0
		for i in range(len(str)):
			for j in range(i, len(str), 1):
				flag = 1
				for k in range((j - i + 1) // 2):
					if str[i + k] != str[j - k]:
						flag = 0
				if flag != 0 and j - i + 1 > maxLength:
					start = i
					maxLength = j - i + 1
		return maxLength