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 java.io.*;
import java.text.DecimalFormat;
import java.util.*;
public class Template {
	//static int cnt=0;
static Scanner sc=new Scanner(System.in);
	static ArrayList<Long> v=new ArrayList();;
	static int max=1;
	static ArrayList<Integer>[] pair;
	static boolean[] dn;
	static long[] arr;
    static	ArrayList<Long> mLang=new ArrayList();
    static ArrayList<Long> indx;
	static String f3="";
	static Map<Long,Long> s_lcnt=new HashMap();
	static BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); 
	
	public static void main (String[] args) throws java.lang.Exception{
int t=sc.nextInt();
while(t-->0) {
	int n=sc.nextInt();
	ArrayList<Integer> arr=new ArrayList();
	arr=arrInpInt(n);
	
	boolean[] dn=new boolean[n];
	int colors=0;
	for(int i=0;i<n;i++) {
		if(!dn[i]) {
			//System.out.println(i);
			colors++;
			dn[i]=true;
			int pv=arr.get(i);
			for(int j=i+1;j<n;j++) {
				if( !dn[j] && arr.get(j)>pv) {
					dn[j]=true;
					pv=arr.get(j);
				}
			}
		}
		
	}
	
	System.out.println(colors);
}

	}
	
	
	
	
	
	
	
	
	public static long fact(long i) {
	long fact=1;
		for(int j=2;j<=i;j++) {
			fact=fact*j;
		}
		return fact;
	}
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	public static void printArrInt(ArrayList<Integer> arr) {
		for(int i=0;i<arr.size();i++) {
			System.out.print(arr.get(i)+" ");
	}	
		}
	
	public static int[][] matrixInp(int n,int m) {
		int[][] arr=new int[n][m];
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				arr[i][j]=sc.nextInt();
			}
		}
		return arr;
	}
	
	
	
	
	
	
	public static int bSearch(ArrayList<Long> arr,long n) {
		
		int start=0;
		int end=arr.size()-1;
		int mid=0;
		while(end>=start) {
		mid=start+(end-start)/2;
		if(arr.get(mid)==n) {
			break;
			
		}
		else if(arr.get(mid)>n) {
			end=mid-1;
		}
		else if(arr.get(mid)<n) {
			start=mid+1;
		}
		}
		return mid;
	}
	

	
	public static int reduceFraction(int a, int b)
	{
		int aa=a;
		if(a==0 || b==0)
			return Math.max(a, b);
		else {
			for(int i=2;i<=Math.min(a, b);i++) {
				if(a%i==0 && b%i==0) {
					a=a/i;
					b=b/i;
					i--;
				}
			}
			
			
		}
		
		return aa/a;
	}
	
	public static long sumDigits(long x) {
		String s=String.valueOf(x);
		//System.out.println(s+" "+sx+" "+x);
		long sum=0;
		for(int i=0;i<s.length();i++) {
			sum+=Long.parseLong(s.substring(i,i+1));
		}
		return sum;
	}
	
	
	public static int[] primeFactofNumb(int num) {
		int[] factors=new int[num+1];
		for(int j=2;j<=Math.sqrt(num);j++) {
			if(num%j==0) {
				factors[j]++;
			}
			while(num%j==0) {
				num=num/j;
			}
			
		}
		
		if(num>1)
			factors[num]++;
		return factors;
	}
	
	
	
	
	public static long nCr(int n, int k){ 
		long C[][] = new long[n + 1][k + 1];
        long i, j;
 
        // Calculate  value of Binomial
        // Coefficient in bottom up manner
        for (i = 0; i <= n; i++) {
            for (j = 0; j <= (long)Math.min(i, k); j++) {
                // Base Cases
                if (j == 0 || j == i)
                    C[(int) i][(int) j] = 1;
 
                // Calculate value using
                // previously stored values
                else
                    C[(int) i][(int) j] = C[(int) (i - 1)][(int) (j - 1)] + C[(int) (i - 1)][(int) j];
            }
        }
 
        return C[n][k];
	}
		
	
		
	

	
	
	

		
	
	
	
	
static long gcd(long a,long b) {
		
	
		if(b==0) {
		return a;
		}
		else if(a==0)
			return b;
			
		
	return gcd(b,a%b);
	
	}
	
	
	
	
	
	public static int s2i(String s) {
		return Integer.parseInt(s);
	}
	

	
	
	public static int LeastIntFn(int a,int b) {
		if((b%a)==0) {
			return (int)b/a;
		}
		return (int)(b/a)+1;
	}
	
	
	
	public static ArrayList<Long> arrInpLong(long n){
		ArrayList<Long> arr=new ArrayList();
		for(long i=0;i<n;i++) {
		arr.add(sc.nextLong());	
		}
		return arr;
	}
	public static ArrayList<String> arrInpStr(int n){
		ArrayList<String> arr=new ArrayList();
		for(int i=0;i<n;i++) {
					arr.add(sc.nextLine());	
		}
		return arr;
	}
	
	public static ArrayList<Integer> arrInpInt(int n){
		ArrayList<Integer> arr=new ArrayList();
		for(int i=0;i<n;i++) {
			int k=sc.nextInt();
			if(k>max)
				max=k;
		arr.add(k);	
		}
		return arr;
	}
	
	

	
	
	public static int min(int a,int b,int c) {
		int min1=Math.min(a, b);
		return Math.min(min1,c);
	}
}