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].
from sys import stdin,stdout
#input=stdin.readline
t=int(input())
from collections import Counter
from math import sqrt,ceil
#count=0
#dp=[['' for i in range(5*10**7)] for j in range(26)]
#[int(x) for x in input().strip().split()]

def factorials(n,r):
    #This calculates ncr mod 10**9+7
    slr=n;dpr=r
    qrr=1;qs=1
    mod=10**9+7
    
    for ip in range(slr-dpr+1,slr+1):
        qlr=(qlr*ip)%mod
    for ij in range(1,dpr+1):
        qs=(qs*ip)%mod
    ans=(qlr*modInverse(qs))%mod
    return ans
def ps(n):
    for ps in range(3,ceil(sqrt(n))+1,2):
        while n%ps==0:
            return False
            
    return True
        
def modInverse(b):
    qr=10**9+7
    return pow(b, qr - 2,qr)
    

for jj in range(t):
    ql=int(input())
    arr=[int(x) for x in input().strip().split()]
    qp=Counter(arr)
    ml=1
    for ps in qp:
        ml=max(ml,qp[ps])
    print(ml)
    
    
    
    
    
    
        
    
    
    
    
        
        
        
        
            
        
    
    
