Define a cyclic sequence of size $n$ as an array $s$ of length $n$, in which $s_n$ is adjacent to $s_1$.

Muxii has a ring represented by a cyclic sequence $a$ of size $n$.

However, the ring itself hates equal adjacent elements. So if two adjacent elements in the sequence are equal at any time, one of them will be erased immediately. The sequence doesn't contain equal adjacent elements initially.

Muxii can perform the following operation until the sequence becomes empty:

Choose an element in $a$ and erase it.

For example, if ring is $[1, 2, 4, 2, 3, 2]$, and Muxii erases element $4$, then ring would erase one of the elements equal to $2$, and the ring will become $[1, 2, 3, 2]$.

Muxii wants to find the maximum number of operations he could perform.

Note that in a ring of size $1$, its only element isn't considered adjacent to itself (so it's not immediately erased).


-----Input-----

Each test contains multiple test cases. The first line contains a single integer $t$ ($1\leq t\leq 100$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $n$ ($1\leq n\leq 100$) — the size of the cyclic sequence.

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1\leq a_i\leq n$) — the sequence itself.

It's guaranteed that $a_i\ne a_{i+1}$ for $1\leq i<n$.

It's guaranteed that $a_n\ne a_1$ when $n>1$.


-----Output-----

For each test case, output a single integer — the maximum number of operations Muxii can perform.


-----Examples-----

Input
3
4
1 2 3 2
4
1 2 1 2
1
1
Output
4
3
1


-----Note-----

In the first test case, you can erase the second element first, then erase the remaining elements one by one in any order. In total, you can perform the operation $4$ times. Note that if you erase the first element first, then the sequence will be turned into $[2,3,2]$ and then immediately become $[2,3]$.

In the second test case, you can erase the first element first, then the sequence becomes $[2,1]$. Then you can erase all remaining elements one by one in any order.

Source: codeforces | Difficulty: EASY
Tags: Greedy algorithms

Implementation

Constructive algorithms


Solutions:
t = int(input())
while t:
	n = int(input())
	a = [int(x) for x in input().split()]
	s = set(a)
	sum = 0
	if len(s) > 2:
		print(n)
	elif len(s) == 1:
		print(1)
	else:
		print(2 + (n - 2) // 2)
	t -= 1


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n == 1:
		print(1)
		continue
	d = {}
	for i in range(n):
		d[a[i]] = d.get(a[i], 0)
		if a[i - 1] == a[(i + 1) % n]:
			d[a[i]] += 1
	k = min(d.values())
	if k == 0 or len(d) > 2:
		print(n)
	else:
		p = n
		for z in d:
			if d[z] == k:
				p = min(p, a.count(z))
		if p == 1:
			print(n)
		else:
			print(n + 1 - k)


for jj in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()]
	if len(set(arr)) == 2:
		print(n // 2 + 1)
	else:
		print(n)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	aa = set(a)
	cont = n if len(aa) > 2 else n // 2 + 1
	print(cont)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ln = len(set(arr))
	print(n // 2 + 1 if ln == 2 else n)


n = input()
for i in range(int(n)):
	ns = int(input())
	seq = input()
	seq = [int(x) for x in seq.split(' ')]
	unq = set(seq)
	if len(unq) > 2:
		print(ns)
	else:
		print(ns // 2 + 1)


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	s = set(l)
	if len(s) > 2:
		print(n)
	else:
		print(n // 2 + 1)


for _ in range(int(input())):
	a = input()
	t = [int(i) for i in input().split()]
	if len(set(t)) != 2:
		print(a)
	else:
		print(len(t) // 2 + 1)


t = int(input())
for i in range(t):
	n = int(input())
	L1 = list(map(int, input().split()))
	K = set(L1)
	k1 = len(K)
	if k1 > 2:
		print(len(L1))
	elif k1 == 2:
		print(len(L1) // 2 + 1)
	else:
		print(1)


import sys
R = sys.stdin.readline
for _ in range(int(R())):
	n = int(R())
	a = [*map(int, R().split())]
	if n <= 2:
		print(n)
		continue
	if len(set(a)) >= 3:
		print(n)
	else:
		print(n // 2 + 1)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if n < 4:
		print(n)
		continue
	c = 0
	for i in range(n):
		if a[i] == a[i - 2]:
			c += 1
	if c == n:
		print(n // 2 + 1)
	else:
		print(n)


I = input
for _ in ' ' * int(I()):
	n = int(I())
	print([n, 1 + n // 2][len(set(I().split())) == 2])


def solve(seq):
	distinct_nr = len(set(seq))
	if distinct_nr > 2:
		return len(seq)
	if len(seq) <= 2:
		return len(seq)
	return len(seq) // 2 + 1

def run_solve():
	n = int(input())
	seq = tuple((int(x) for x in input().split()))
	print(solve(seq))
tests_nr = int(input())
for test in range(tests_nr):
	run_solve()


def main(x, n):
	m = {}
	for xx in x:
		if xx in m:
			m[xx] += 1
		else:
			m[xx] = 1
	if n % 2 == 0 and len(m) == 2:
		return n - (n // 2 - 1)
	else:
		return n
t = int(input())
for i in range(t):
	n = int(input())
	print(main(list(map(lambda x: int(x), input().split())), n))


from collections import defaultdict
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	count = defaultdict(lambda : 0)
	for v in a:
		count[v] += 1
	if len(count) == 2:
		print((len(a) - 2) // 2 + 2)
	else:
		print(len(a))


def solve_case():
	_ = int(input())
	l = list(map(int, input().split()))
	d = set()
	for el in l:
		d.add(el)
	if len(d) == 2:
		print(2 + (len(l) - 2) // 2)
	else:
		print(len(l))
t = int(input())
for _ in range(t):
	solve_case()


import sys
T = int(sys.stdin.readline().strip())
for t in range(0, T):
	n = int(sys.stdin.readline().strip())
	a = len(set(sys.stdin.readline().strip().split()))
	if a == 2:
		print(n // 2 + 1)
	else:
		print(n)


t = int(input())
for _ in range(t):
	n = int(input())
	numbers = [int(x) for x in input().split()]
	if n % 2 == 0:
		p1 = numbers[0]
		p2 = numbers[1]
		works = True
		for i in range(n // 2):
			if numbers[2 * i] != p1 or numbers[2 * i + 1] != p2:
				works = False
				break
		if not works:
			print(n)
		else:
			print(n // 2 + 1)
	else:
		print(n)


try:
	for _ in range(int(input())):
		n = int(input())
		lst = list(map(int, input().split()))
		if n == 1:
			print(1)
			continue
		if len(set(lst)) == 2:
			n = n // 2 + 1
		print(n)
except Exception as e:
	print(e)


t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	key = 0
	for i in range(n):
		if i % 2 == 0:
			if arr[i] != arr[0]:
				key = 1
				break
		elif arr[i] != arr[1]:
			key = 1
			break
	if key == 1:
		print(n)
	else:
		print(n // 2 + 1)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	a = n
	if len(set(l)) == 2:
		if n % 2 == 0:
			l1 = []
			for i in range(n):
				if i % 2 == 0:
					l1.append(l[0])
				else:
					l1.append(l[1])
			if l == l1:
				a = a // 2
				a += 1
	print(a)


t = int(input())
answer1 = 'Yes'
answer2 = 'No'
zero = 0
one = 1
two = 2

def main():
	for q in range(t):
		dict = {}
		number = int(input())
		Array = list(map(int, input().split()))
		res = zero
		for j in range(number):
			if Array[j] not in dict.keys():
				dict[Array[j]] = one
			elif dict[Array[j]] == one:
				res = res + one
		if res != number - two:
			print(number)
		else:
			print(two + int((number - two) / two))
main()


import math
testcases = int(input())
while testcases > 0:
	testcases -= 1
	n = int(input())
	array = [int(x) for x in input().split()]
	distinct = []
	flag = True
	for element in array:
		if element not in distinct:
			distinct.append(element)
		if len(distinct) > 2:
			flag = False
			break
	if flag == False:
		print(n)
	elif n >= 4:
		value = max(n - 4, 0) / 2 + 3
		print(int(value))
	else:
		print(n)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	mp = {}
	for i in range(len(arr)):
		mp[arr[i]] = 1
	res = list(mp.keys())
	if len(res) > 2:
		print(n)
	else:
		print(2 + (n - 2) // 2)


t = int(input())
for i in range(t):
	n = int(input())
	a = input()
	b = a.split()
	for j in range(n):
		b[j] = int(b[j])
	k = 1
	if n % 2 == 0 and n > 2:
		s = 0
		for j in range(n):
			if j <= n - 3:
				if b[j] == b[j + 2]:
					s += 1
		if b[n - 2] == b[0]:
			s += 1
		if b[n - 1] == b[1]:
			s += 1
		if s == n:
			k = 0
	if k == 1:
		print(n)
	else:
		print(n // 2 + 1)


t = int(input())
for test in range(t):
	n = int(input())
	a = input().split()
	for i in range(n):
		a[i] = int(a[i])
	if n == 1:
		print(1)
		continue
	cnt = []
	for i in range(n + 1):
		cnt.append(0)
	for b in a:
		cnt[b] = 1
	many = 0
	for b in cnt:
		many += b
	if many > 2:
		print(n)
	if many == 2:
		k = n // 2
		ans = 1 + k
		print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	cnt_array = [0 for i in range(n)]
	for x in a:
		cnt_array[x - 1] = 1
	cnt_distinct = sum(cnt_array)
	if n == 1:
		answer = 1
	elif cnt_distinct == 2:
		answer = n // 2 + 1
	else:
		answer = n
	print(answer)


T = int(input())
for _ in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	st = set([])
	for x in a:
		st.add(x)
	if len(st) > 2:
		print(n)
	elif len(st) == 1:
		print(1)
	else:
		print(2 + (n - 2) // 2)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	arr = list(map(int, input().split()))
	dup = list(set(arr))
	if len(dup) > 2:
		print(n)
	elif len(dup) == 1:
		print(1)
	else:
		print(int(2 + (n - 2) / 2))


import sys

def input():
	return sys.stdin.readline().rstrip('\r\n')

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	s = set(a)
	if len(s) == 1:
		return 1
	if len(s) > 2:
		return n
	return 2 + (n - 2) // 2
t = int(input())
for _ in range(t):
	print(solve())


for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	ans = 0
	if len(set(nums)) == 1:
		ans = 1
	elif len(set(nums)) > 2:
		ans = n
	else:
		ans = 2 + (n - 2) // 2
	print(ans)


import math
from collections import Counter

def li():
	return list(map(int, input().split()))

def n():
	return int(input())

def st():
	return input()
yes = 'YES'
no = 'NO'
even = 'EVEN'
odd = 'ODD'

def prefix(L):
	size = len(L)
	for i in range(1, size):
		L[i] = L[i] + L[i - 1]
	return L
for _ in range(int(input())):
	size = n()
	L = li()
	s = set(L)
	if size == 1:
		print(1)
	elif len(s) == 2:
		print(2 + (size - 2) // 2)
	else:
		print(size)


for s in [*open(0)][2::2]:
	n = len((a := s.split()))
	print((n, n // 2 + 1)[len({*a}) == 2])


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if len(a) % 2 == 1:
		print(len(a))
	elif len(set(a)) == 2:
		print(len(a) // 2 + 1)
	else:
		print(len(a))


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(ii) for ii in input().split()]
	if n == 1:
		print(1)
		continue
	if len(set(a)) == 2:
		print(n // 2 + 1)
	else:
		print(n)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	a.sort()
	if n % 2 == 1:
		print(n)
	elif a[0] == a[n // 2 - 1] and a[n // 2] == a[n - 1]:
		print(n // 2 + 1)
	else:
		print(n)


def solve():
	n = int(input())
	arr = [int(x) for x in input().split()]
	if n == 1 or n == 2:
		print(n)
		return
	if n % 2 == 0:
		first = arr[0]
		second = arr[1]
		flag1 = 0
		flag2 = 0
		for i in range(2, n, 2):
			if arr[i] != first:
				flag1 = 1
		for i in range(3, n, 2):
			if arr[i] != second:
				flag2 = 1
		if (flag1 or flag2) == 0:
			ans = n // 2 + 1
			print(ans)
		else:
			print(n)
	else:
		print(n)
t = int(input())
for i in range(t):
	solve()


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	k1 = 0
	j = 0
	while j < len(a) - 1 and a[j - 1] == a[j + 1]:
		k1 += 1
		j += 2
	j = 1
	k2 = 1
	while j < len(a) - 1 and a[j - 1] == a[j + 1]:
		k2 += 1
		j += 2
	if n % 2 == 0 and k1 == n / 2 and (k2 == n / 2):
		print(n // 2 + 1)
	else:
		print(n)


for tc in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	x = set(a)
	if len(x) > 2:
		print(n)
	elif len(x) == 1:
		print(1)
	else:
		ans = 2 + (n - 2) // 2
		print(ans)


t = int(input())
for p in range(t):
	n = int(input())
	flag = True
	a = list(map(int, input().split()))
	b = [0] * 101
	for i in range(n):
		x = a[i]
		b[x] += 1
	minim = n
	for i in range(101):
		if b[i] != 0 and b[i] < minim:
			minim = b[i]
	if minim == n // 2:
		print(n - minim + 1)
	else:
		print(n)


T = int(input())
for i in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	s = set(a)
	if len(s) > 2:
		print(n)
	elif len(s) == 1:
		print(1)
	else:
		k = n - 2
		print(2 + k // 2)


t = int(input())
while t > 0:
	n = int(input())
	L = list(map(int, input().split()))
	ret = 0
	while len(L) > 1:
		length = len(L)
		sign = 1
		temp = L[0]
		for i in range(1, length):
			if i == length - 1:
				if L[i - 1] != L[0]:
					sign = 0
				break
			if L[i - 1] != L[i + 1]:
				sign = 0
				break
		if sign:
			ret += len(L) // 2
			break
		else:
			ret += len(L) - 1
			break
	ret += 1
	print(ret)
	t -= 1


import math
for _ in range(int(input())):
	n = int(input())
	l = map(int, input().split())
	if len(set(l)) == 2:
		print(int(n / 2 + 1))
	else:
		print(n)


n = int(input())
for i in range(n):
	l = int(input())
	L = [int(s) for s in input().split()]
	if l < 4:
		print(l)
	else:
		check = 0
		for i in range(0, l - 2):
			if L[i] != L[i + 2]:
				check = 1
		if check == 1:
			print(l)
		else:
			print(l // 2 + 1)


for _ in range(int(input())):
	p = int(input())
	x = list(map(int, input().split()))
	r = set()
	for k in x:
		r.add(k)
	if len(r) > 2:
		print(int(p))
	elif len(r) == 1:
		print(int(1))
	else:
		print(int(2 + (p - 2) / 2))


t = int(input())
for i in range(t):
	n = int(input())
	x = list(map(int, input().split()))
	if n == 1:
		print(n)
		continue
	a = x[0]
	b = x[1]
	y = n % 2 == 1
	Ans = 0
	if n % 2 == 0:
		for i in range(0, n - 1, 2):
			if x[i] != a or x[i + 1] != b:
				y = True
	if y == False:
		Ans = n // 2 + 1
	else:
		Ans = n
	print(Ans)


for t in range(0, int(input())):
	n = int(input())
	ring = list(map(int, input().split()))
	is_in_cycle = True
	for i in range(0, n):
		if ring[i % 2] != ring[i]:
			is_in_cycle = False
	if is_in_cycle:
		print(n // 2 + 1)
	else:
		print(n)


import sys
FILE = False
if FILE:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def get_int():
	return int(sys.stdin.readline())

def get_string():
	return sys.stdin.readline().strip()
test_cases = get_int()
for test in range(test_cases):
	n = get_int()
	input = [int(x) for x in get_string().split()]
	if len(set(input)) >= 3:
		print(n)
	elif len(set(input)) == 1:
		print(1)
	else:
		print((n - 2) // 2 + 2)


testcases = int(input())
for i in range(testcases):
	n = int(input())
	li = list(map(int, input().split()))
	a = {}
	a = set()
	for i in li:
		a.add(i)
	if len(a) > 2:
		print(n)
	elif len(a) == 1:
		print(1)
	else:
		print(2 + (n - 2) // 2)


from math import floor

def alternate(x, n):
	for i in range(0, n, 2):
		if x[i] != x[0]:
			return 0
	for i in range(1, n, 2):
		if x[i] != x[1]:
			return 0
	return 1
for _ in range(int(input())):
	n = int(input())
	ar = [int(x) for x in input().split()]
	if n == 1:
		print(1)
	elif n == 2:
		print(2)
	elif alternate(ar, n):
		print(floor(n / 2) + 1)
	else:
		print(n)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	S = set([])
	for i in A:
		S.add(i)
	ans = 0
	sn = len(S)
	if sn == 1:
		print(1)
	elif sn == 2:
		print((N - 2) // 2 + 2)
	else:
		print(N)


import sys
input = sys.stdin.readline
out = []
t = int(input())
for _ in range(t):
	n = int(input())
	data = input().split()
	for i in range(2, n):
		if data[i] != data[i - 2]:
			out.append(n)
			break
	else:
		out.append(n // 2 + 1)
print('\n'.join(map(str, out)))


import math
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	set1 = list(set(arr))
	if len(set1) > 2:
		print(n)
	elif len(set1) == 1:
		print(1)
	else:
		print(int(2 + (n - 2) / 2))


for _ in range(int(input())):
	n = int(input())
	print(n // 2 + 1 if len(set(map(int, input().split()))) == 2 else n)


test = int(input())
while test:
	n = int(input())
	a = [int(x) for x in input().split()]
	if len(set(a)) == 1:
		print(1)
	elif len(set(a)) == 2:
		print(n // 2 + 1)
	else:
		print(n)
	test -= 1


for _ in range(int(input())):
	n = int(input())
	s = set(map(int, input().split()))
	cnt = len(list(s))
	if cnt == 2:
		ans = n // 2 + 1
	else:
		ans = n
	print(ans)


from collections import Counter
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	c = Counter(a)
	print(n // 2 + 1 if len(c) == 2 else n)


from typing import List
from collections import *
import math

class Solution:

	def begin2(self, n: int, nums: List[int]):
		res = 0
		left = 0
		while left < len(nums) - 1 and len(nums) > 2:
			print(nums)
			if nums[left - 1] != nums[left + 1]:
				nums = nums[:left] + nums[left + 1:]
				res += 1
				if left > 0:
					left -= 1
			else:
				left += 1
		if len(nums) <= 2:
			res += len(nums)
		else:
			res += (len(nums) - 2) // 2 + 2
		print(res)

	def begin(self, n: int, nums: List[int]):
		c = Counter(nums)
		print(n // 2 + 1 if len(c) == 2 else n)
		return
sol = Solution()
caseNum = int(input())
for i in range(0, caseNum):
	n = int(input())
	allnums = input().split(' ')
	nums = []
	for t in allnums:
		nums.append(int(t))
	sol.begin(n, nums)


for i in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	d = {}
	for i in a:
		d[i] = d.get(i, 0) + 1
	if len(d) == 2:
		print(n // 2 + 1)
	else:
		print(n)


from collections import *

def solve():
	n = int(input())
	a = [int(i) for i in input().split()]
	if len(list(set(a))) == 2:
		print(n // 2 + 1)
	else:
		print(n)
t = int(input())
for _ in range(t):
	solve()


import sys
from collections import *
sys.setrecursionlimit(10 ** 5)
itr = (line for line in sys.stdin.read().strip().split('\n'))
INP = lambda : next(itr)

def ni():
	return int(INP())

def nl():
	return [int(_) for _ in INP().split()]

def solve(n, a):
	seen = {}
	for e in a:
		if e not in seen:
			seen[e] = 1
		else:
			seen[e] += 1
	u = len(seen.keys())
	if u == 2:
		print(1 + n // 2)
	else:
		print(n)
t = ni()
for case in range(t):
	n = ni()
	a = nl()
	solve(n, a)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	d = set(l)
	if len(d) == 1:
		print(1)
	elif len(d) == 2:
		m = int((n - 2) / 2)
		print(m + 2)
	else:
		print(n)


t = int(input())

def solve():
	n = int(input())
	arr = set(map(int, input().split()))
	if len(arr) == 2:
		return n // 2 + 1
	return n
for i in range(t):
	print(solve())


t = eval(input())
B = []
for i in range(t):
	n = eval(input())
	str_in = input()
	A = set(map(int, str_in.strip().split()))
	if len(A) == 2:
		B.append(int(n / 2 + 1))
	else:
		B.append(n)
for i in B:
	print(i)


t = int(input())
for i in range(t):
	n = int(input())
	a = input()
	a = a.split()
	a = [int(x) for x in a]
	a_set = set(a)
	if len(a_set) > 2:
		rez = len(a)
	else:
		rez = len(a) // 2 + 1
	print(rez)


import sys
input = sys.stdin.readline

def readList():
	return list(map(int, input().split()))

def readInt():
	return int(input())

def readInts():
	return map(int, input().split())

def readStr():
	return input().strip()

def solve():
	n = readInt()
	arr = readList()
	ans = 0
	while True:
		m = len(arr)
		tmp = []
		for i in range(m):
			if arr[(i - 1) % m] != arr[(i + 1) % m]:
				ans += 1
				continue
			tmp.append(i)
		if m == len(tmp):
			break
		arr = tmp
	arr = tmp
	return min((n - ans) // 2 + 1 + ans, n)
for _ in range(int(input())):
	print(solve())


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	m = len(set(a))
	if n > 2 and m == 2:
		n -= m
		p = (n + 1) // 2
		print(p + 2)
	else:
		print(n)


for i in range(int(input())):
	a = int(input())
	x = list(map(int, input().split()))
	l = len(set(x))
	if l == 2:
		ans = a // 2 + 1
	else:
		ans = a
	print(ans)


def main():
	t = int(input())
	for i in range(t):
		n = int(input())
		a = list(map(int, input().split()))
		_a = set(a)
		cont = n if len(_a) > 2 else n // 2 + 1
		print(cont)
main()


t = int(input())
result = []
for i in range(t):
	n = int(input())
	d = {}
	tab = list(map(int, input().split(' ')))
	c = 0
	for i in tab:
		if i not in d:
			c += 1
			d[i] = 1
		if c == 3:
			result.append(n)
			break
	if c <= 2:
		result.append(n // 2 + 1)
for i in result:
	print(i)


t = int(input())
while t:
	n = int(input())
	count = 0
	a = list(map(int, input().split()))[:n]
	count = len(set(a))
	if count > 2:
		print(n)
	elif n == 1:
		print(1)
	else:
		print(int(n / 2 + 1))
	t -= 1


t = int(input())
while t > 0:
	n = int(input())
	lst = set(map(int, input().strip().split()))
	size = len(lst)
	if size < 3:
		print(int(n / 2) + 1)
	else:
		print(n)
	t -= 1


t = int(input())
while t > 0:
	n = int(input())
	inp = list(map(int, input().split()))
	k = len(set(inp))
	if k != 2:
		print(n)
	else:
		print(int(n / 2 + 1))
	t -= 1


n = int(input())
for _ in range(n):
	n = int(input())
	l = [int(i) for i in input().split()]
	s = set(l)
	if len(s) > 2 or len(s) == 1:
		print(n)
	else:
		print(n // 2 + 1)


t = int(input())
for k in range(t):
	n = int(input())
	val = input().split(' ')
	val = {int(i) for i in val}
	if len(val) > 2:
		print(n)
	else:
		print(int(n / 2 + 1))


t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	s = [int(i) for i in input().split(' ')]
	if n == 1:
		print(1)
		continue
	OK = True
	previous = -1
	index = {}
	for i in s:
		if not str(i) in index:
			index.update({str(i): 1})
		else:
			index.update({str(i): index[str(i)] + 1})
	for i in index:
		if previous == -1:
			previous = index[i]
			continue
		if index[i] != previous:
			OK = False
			break
	if len(index) == 2 and OK == True:
		print(n // 2 + 1)
	else:
		print(n)


def maxi(n, arr):
	if len(set(arr)) == 2:
		return n // 2 + 1
	else:
		return n
t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	print(maxi(n, arr))


t = int(input())
for i in range(t):
	n = int(input())
	nums = list(map(int, input().split()))
	dist = set(nums)
	if len(dist) == 1:
		print(1)
	elif len(dist) == 2:
		print(n // 2 + 1)
	else:
		print(n)