Nezzar has n balls, numbered with integers 1, 2, …, n. Numbers a_1, a_2, …, a_n are written on them, respectively. Numbers on those balls form a non-decreasing sequence, which means that a_i ≤ a_{i+1} for all 1 ≤ i < n.

Nezzar wants to color the balls using the minimum number of colors, such that the following holds.

  * For any color, numbers on balls will form a strictly increasing sequence if he keeps balls with this chosen color and discards all other balls. 



Note that a sequence with the length at most 1 is considered as a strictly increasing sequence.

Please help Nezzar determine the minimum number of colors.

Input

The first line contains a single integer t (1 ≤ t ≤ 100) — the number of testcases. 

The first line of each test case contains a single integer n (1 ≤ n ≤ 100).

The second line of each test case contains n integers a_1,a_2,…,a_n (1 ≤ a_i ≤ n). It is guaranteed that a_1 ≤ a_2 ≤ … ≤ a_n.

Output

For each test case, output the minimum number of colors Nezzar can use.

Example

Input


5
6
1 1 1 2 3 4
5
1 1 2 2 3
4
2 2 2 2
3
1 2 3
1
1


Output


3
2
4
1
1

Note

Let's match each color with some numbers. Then:

In the first test case, one optimal color assignment is [1,2,3,3,2,1].

In the second test case, one optimal color assignment is [1,2,1,2,1].
import heapq as hq
from heapq import heappop,heappush
from collections import deque,defaultdict,Counter
from sys import stdin,stdout


def inp():
	return int(stdin.readline())


def inlt():
	return list(map(int,stdin.readline().split()))


def insr():
	return list(stdin.readline().strip())


def invr():
	return map(int,stdin.readline().split())


def pr(n):
	stdout.write(str(n)+"\n")


def subset_sum_count(arr,n,sum):
	dp=[[0 for _ in range(sum+1)] for _ in range(n+1)]
	for i in range(n+1):
		for j in range(sum+1):
			if j==0:
				dp[i][j]=1
			elif arr[i-1]<=j:
				dp[i][j]=dp[i-1][j-arr[i-1]]+dp[i-1][j]
			else:
				dp[i][j]=dp[i-1][j]
	return dp[n][sum]


def binary_search(func,lo,hi,abs_prec=1e-7):
	""" Locate the first value x s.t. func(x) = True within [lo, hi] """
	while abs(hi-lo)>abs_prec:
		mi=lo+(hi-lo)/2
		if func(mi):
			hi=mi
		else:
			lo=mi
	
	return (lo+hi)/2


def ternary_search(func,lo,hi,abs_prec=1e-7):
	""" Find maximum of unimodal function func() within [lo, hi] """
	while abs(hi-lo)>abs_prec:
		lo_third=lo+(hi-lo)/3
		hi_third=hi-(hi-lo)/3
		
		if func(lo_third)<func(hi_third):
			lo=lo_third
		else:
			hi=hi_third
	
	return (lo+hi)/2


def discrete_binary_search(func,lo,hi):
	""" Locate the first value x s.t. func(x) = True within [lo, hi] """
	while lo<hi:
		mi=lo+(hi-lo)//2
		if func(mi):
			hi=mi
		else:
			lo=mi+1
	
	return lo


def discrete_ternary_search(func,lo,hi):
	""" Find the first maximum of unimodal function func() within [lo, hi] """
	while lo<=hi:
		lo_third=lo+(hi-lo)//3
		hi_third=lo+(hi-lo)//3+(1 if 0<hi-lo<3 else (hi-lo)//3)
		
		if func(lo_third)<func(hi_third):
			lo=lo_third+1
		else:
			hi=hi_third-1
	
	return lo
	
	return -1


def right_rotate(a,s):
	return a[s:]+a[:s]


def dec_to_bin(x):
	return int(bin(x)[2:])


def str_to_integer_list(n):
	a=[]
	for i in range(len(n)):
		a.append(int(n[i]))
	return a


def list_to_str(l):
	s=""
	for i in l:
		s+=str(i)
	return s


def dijkstra(s,N,E):
	visited=set()
	dist={}
	for i in range(1,N+1):
		dist[i]=1<<29
	queue=[(dist[i],i) for i in range(1,N+1)]
	hq.heappush(queue,(0,s))
	dist[s]=0
	while queue:
		d,u=hq.heappop(queue)
		if u in visited:
			continue
		#Relax all the neighbours of u
		for t in E[u]:
			v,r=t
			if dist[v]>d+r:
				dist[v]=d+r
				hq.heappush(queue,(dist[v],v))
		#Node u has been processed
		visited.add(u)
	return dist


def prime_sieve(n):
	"""returns a sieve of primes >= 5 and < n"""
	flag=n%6==2
	sieve=bytearray((n//3+flag>>3)+1)
	for i in range(1,int(n**0.5)//3+1):
		if not (sieve[i>>3]>>(i&7))&1:
			k=(3*i+1)|1
			for j in range(k*k//3,n//3+flag,2*k):
				sieve[j>>3]|=1<<(j&7)
			for j in range(k*(k-2*(i&1)+4)//3,n//3+flag,2*k):
				sieve[j>>3]|=1<<(j&7)
	return sieve


def prime_list(n):
	"""returns a list of primes <= n"""
	res=[]
	if n>1:
		res.append(2)
	if n>2:
		res.append(3)
	if n>4:
		sieve=prime_sieve(n+1)
		res.extend(3*i+1|1 for i in range(1,(n+1)//3+(n%6==1)) if not (sieve[i>>3]>>(i&7))&1)
	return res


def dijkstra(n,graph,start):
	""" Uses Dijkstra's algortihm to find the shortest path between in a graph. """
	dist,parents=[float("inf")]*n,[-1]*n
	dist[start]=0
	queue=[(0,start)]
	while queue:
		path_len,v=heappop(queue)
		if path_len==dist[v]:
			for w,edge_len in graph[v]:
				if edge_len+path_len<dist[w]:
					dist[w],parents[w]=edge_len+path_len,v
					heappush(queue,(edge_len+path_len,w))
	
	return dist,parents


def path(start,end,parent):
	path=[end]
	while path[-1]!=start:
		path.append(parent[path[-1]])
	path.reverse()
	return path


def bfs(graph,start,goal):
	"""
	finds a shortest path in undirected `graph` between `start` and `goal`.
	If no path is found, returns `None`
	"""
	if start==goal:
		return [start]
	visited={start}
	queue=deque([(start,[])])
	
	while queue:
		current,path=queue.popleft()
		visited.add(current)
		for neighbor in graph[current]:
			if neighbor==goal:
				return path+[current,neighbor]
			if neighbor in visited:
				continue
			queue.append((neighbor,path+[current]))
			visited.add(neighbor)
	return None  # no path found. not strictly needed


def fillPrefixSum(arr,n,prefixSum):
	prefixSum[0]=arr[0]
	
	# Adding present element
	# with previous element
	for i in range(1,n):
		prefixSum[i]=prefixSum[i-1]+arr[i]


def check(a,ind,d1):
	beg=a[:ind+1]
	end=a[ind+1:]
	d=[]
	c=0
	for i in end:
		if i-d1 in beg:
			c+=1
	return c


'''for _ in range(int(input())):
	n,m=list(map(int,input().split()))
	graph=defaultdict(list)
	distance=[-1]*(n+1)
	visited=[False]*(n+1)
	for _ in range(m):
		x,y=list(map(int,input().split()))
		graph[x].append(y)
		graph[y].append(x)'''
'''for _ in range(int(input())):
	n,m=list(map(int,input().split()))
	graph=[[]for _ in range(n+1)]
	distance=[-1]*(n+1)
	visited=[False]*(n+1)
	for _ in range(m):
		x,y,w=list(map(int,input().split()))
		graph[x].append([y,w])
		graph[y].append([x,w])'''

import os
import sys
from io import BytesIO,IOBase


def DecimalToBinary(n):
	def helper(n):
		if n==0:
			return ''  # <- empty string
		else:
			if n%2==1:
				binaryDigit='1'
			else:
				binaryDigit='0'
			return helper(n//2)+binaryDigit
	
	if n==0:
		result='0'  # <- "leading zero" only for `n == 0`
	else:
		result=helper(n)
	return result


def p(board):
	for i in range(8):
		s=""
		for j in range(8):
			s+=board[i][j]
		print(s)


def binaryToDecimal(n):
	return int(n,2)


def decimalToBinary(n):
	return bin(n).replace("0b","")


def mostFrequent(arr,n):
	# Sort the array
	arr.sort()
	
	# find the max frequency using
	# linear traversal
	max_count=1;
	res=arr[0];
	curr_count=1
	
	for i in range(1,n):
		if (arr[i]==arr[i-1]):
			curr_count+=1
		
		else:
			if (curr_count>max_count):
				max_count=curr_count
				res=arr[i-1]
			
			curr_count=1
	
	# If last element is most frequent
	if (curr_count>max_count):
		max_count=curr_count
		res=arr[n-1]
	
	return res


from bisect import bisect_right,bisect_left


def lds(arr,n):
	lds=[0]*n
	max=0
	
	for i in range(n):
		lds[i]=1
	
	for i in range(1,n):
		for j in range(i):
			if (arr[i]<arr[j] and
					lds[i]<lds[j]+1):
				lds[i]=lds[j]+1
	
	for i in range(n):
		if (max<lds[i]):
			max=lds[i]
	
	# returns the length of the LDS
	return max


import math


def prefix(a):
	pre=[]
	pre.append(a[0])
	for i in range(1,len(a)):
		pre.append(pre[i-1]+a[i])
	return pre


from collections import defaultdict


class Graph:
	def __init__(self,v):
		self.v=v
		self.graph=defaultdict(list)
	
	def add_edge(self,u,v):
		self.graph[u].append(v)
	
	def display(self):
		print(dict(self.graph))
	
	def find_parent(self,parent,i):
		if parent[i]==-1:
			return i
		else:
			return self.find_parent(parent,parent[i])
	
	def union(self,parent,x,y):
		x_set=self.find_parent(parent,x)
		y_set=self.find_parent(parent,y)
		parent[x_set]=y_set
	
	def is_cyclic(self):
		parent=[-1]*(self.v)
		for i in self.graph:
			for j in self.graph[i]:
				x=self.find_parent(i)
				y=self.find_parent(j)
				if x==y:
					return True
				self.union(x,y)


dx=[-1,1,0,0,1,1,-1,-1]
dy=[0,0,1,-1,1,-1,1,-1]


def is_valid(x,y,matrix,vis):
	if x<0 and y<0 and x>=len(matrix) and y>=len(matrix[0]):
		return False
	if vis[x][y]!=1 or matrix[x][y]==0:
		return False
	return True


def dfs(i,j,matrix,vis):
	stack=[(i,j)]
	cc=1
	vis[i][j]=1
	while stack:
		x,y=stack.pop()
		for i in range(8):
			new_x=x+dx[i]
			new_y=y+dy[i]
			if is_valid(new_x,new_y,matrix,vis):
				vis[new_x][new_y]=1
				stack.append((new_x,new_y))
				cc+=1
	return cc


def lcm(a,b):
	return abs(a*b)//math.gcd(a,b)




from itertools import cycle
for _ in range(inp()):
	n = inp()
	a = inlt()
	d = dict(Counter(a))
	res = []
	for i,j in d.items():
		res.append(j)
	print(max(res))
	
	
	
	
	
	
		
	