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.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.function.BiConsumer;
import java.io.IOException;
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;

public class S {
	
	static private long ans;
	static private long count1;
	static private long count2;
	static private long tmp;
	
	private static int[][] arr;
	private static int n;
	
	private static long[] larr;
	private static int r1,r2,r3;
	private static int c1,c2,c3;
	private static int p1,p2,p3;
	private static long r;
	private static long min;
	private static long max;
	
	static class Reader {
		
		static BufferedReader reader;
		static StringTokenizer tokenizer;
		
		static void init(InputStream input) {
			reader = new BufferedReader(new InputStreamReader(input));
			tokenizer = new StringTokenizer("");
		}
		
		static String next() throws IOException {
			while(!tokenizer.hasMoreTokens()) {
				tokenizer = new StringTokenizer(reader.readLine());
			}
			return tokenizer.nextToken();
		}
		
		static int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
		
		static long nextLong() throws IOException {
			return Long.parseLong(next());
		}
		
	}

	static int[] merge(int[] a, int[] b) {
		int m = a.length;
		int n = b.length;
		int [] c = new int[n+m];
		
		int j=0, k=0;
		while(j+k<m+n) {
			if(j>=m) {
				c[j+k] = b[k];
				k++;
			}
			else if(k>=n) {
				c[j+k] = a[j];
				j++;
			}
			else {
				if(a[j]<b[k]) {
					c[j+k] = a[j];
					j++;
				}
				else if(a[j]==b[k]) {
					if(a[j]<b[k]) {
						c[j+k] = a[j];
						j++;
					}
					else {
						c[j+k] = b[k];
						k++;
					}
				}
				else {
					c[j+k] = b[k];
					k++;
				}
			}
		}
		return c;
	}
	
	static int[] Msort(int[] unsorted){
		int l = unsorted.length;
		
		if(l<=1) {
			return unsorted;
		}
		
		else {
			int[] Msorted = new int[l];
			int[] m1 = new int[l/2];
			int[] m2 = new int[l-(l/2)];
			
			for(int i=0; i<l; i++) {
				if(i<l/2) {
					m1[i] = unsorted[i];
				}
				else {
					m2[i-(l/2)] = unsorted[i];
				}
			}
			
			Msorted = merge(Msort(m1), Msort(m2));		
			
			return Msorted;
		}
		
	}
	
	static long[] merge(long[] a, long[] b) {
		int m = a.length;
		int n = b.length;
		long [] c = new long[n+m];
		
		int j=0, k=0;
		while(j+k<m+n) {
			if(j>=m) {
				c[j+k] = b[k];
				k++;
			}
			else if(k>=n) {
				c[j+k] = a[j];
				j++;
			}
			else {
				if(a[j]<b[k]) {
					c[j+k] = a[j];
					j++;
				}
				else if(a[j]==b[k]) {
					if(a[j]<b[k]) {
						c[j+k] = a[j];
						j++;
					}
					else {
						c[j+k] = b[k];
						k++;
					}
				}
				else {
					c[j+k] = b[k];
					k++;
				}
			}
		}
		return c;
	}
	
	static long[] Msort(long[] unsorted){
		int l = unsorted.length;
		
		if(l<=1) {
			return unsorted;
		}
		
		else {
			long[] Msorted = new long[l];
			long[] m1 = new long[l/2];
			long[] m2 = new long[l-(l/2)];
			
			for(int i=0; i<l; i++) {
				if(i<l/2) {
					m1[i] = unsorted[i];
				}
				else {
					m2[i-(l/2)] = unsorted[i];
				}
			}
			
			Msorted = merge(Msort(m1), Msort(m2));		
			
			return Msorted;
		}
		
	}

	static int[][] merge_x(int[][] a, int[][] b) {
		int m = a.length;
		int n = b.length;
		int [][] c = new int[n+m][2];
		
		int j=0, k=0;
		while(j+k<m+n) {
			if(j>=m) {
				c[j+k][0] = b[k][0];
				c[j+k][1] = b[k][1];
				k++;
			}
			else if(k>=n) {
				c[j+k][0] = a[j][0];
				c[j+k][1] = a[j][1];
				j++;
			}
			else {
				if(a[j][0]<b[k][0]) {
					c[j+k][0] = a[j][0];
					c[j+k][1] = a[j][1];
					j++;
				}
				else if(a[j][0]==b[k][0]) {
					if(a[j][1]<b[k][1]) {
						c[j+k][0] = a[j][0];
						c[j+k][1] = a[j][1];
						j++;
					}
					else {
						c[j+k][0] = b[k][0];
						c[j+k][1] = b[k][1];
						k++;
					}
				}
				else {
					c[j+k][0] = b[k][0];
					c[j+k][1] = b[k][1];
					k++;
				}
			}
		}
		return c;
	}
	
	static int[][] Msort_x(int[][] unsorted){
		int l = unsorted.length;
		
		if(l<=1) {
			return unsorted;
		}
		
		else {
			int[][] Msorted = new int[l][2];
			int[][] m1 = new int[l/2][2];
			int[][] m2 = new int[l-(l/2)][2];
			
			for(int i=0; i<l; i++) {
				if(i<l/2) {
					m1[i][0] = unsorted[i][0];
					m1[i][1] = unsorted[i][1];
				}
				else {
					m2[i-(l/2)][0] = unsorted[i][0];
					m2[i-(l/2)][1] = unsorted[i][1];
				}
			}
			
			Msorted = merge_x(Msort_x(m1), Msort_x(m2));
			
			return Msorted;
		}
		
	}
	
	static int[][] merge_y(int[][] a, int[][] b) {
		int m = a.length;
		int n = b.length;
		int [][] c = new int[n+m][2];
		
		int j=0, k=0;
		while(j+k<m+n) {
			if(j>=m) {
				c[j+k][0] = b[k][0];
				c[j+k][1] = b[k][1];
				k++;
			}
			else if(k>=n) {
				c[j+k][0] = a[j][0];
				c[j+k][1] = a[j][1];
				j++;
			}
			else {
				if(a[j][1]<b[k][1]) {
					c[j+k][0] = a[j][0];
					c[j+k][1] = a[j][1];
					j++;
				}
				else if(a[j][1]==b[k][1]) {
					if(a[j][0]<b[k][0]) {
						c[j+k][0] = a[j][0];
						c[j+k][1] = a[j][1];
						j++;
					}
					else {
						c[j+k][0] = b[k][0];
						c[j+k][1] = b[k][1];
						k++;
					}
				}
				else {
					c[j+k][0] = b[k][0];
					c[j+k][1] = b[k][1];
					k++;
				}
			}
		}
		return c;
	}
	
	static int[][] Msort_y(int[][] unsorted){
		int l = unsorted.length;
		
		if(l<=1) {
			return unsorted;
		}
		
		else {
			int[][] Msorted = new int[l][2];
			int[][] m1 = new int[l/2][2];
			int[][] m2 = new int[l-(l/2)][2];
			
			for(int i=0; i<l; i++) {
				if(i<l/2) {
					m1[i][0] = unsorted[i][0];
					m1[i][1] = unsorted[i][1];
				}
				else {
					m2[i-(l/2)][0] = unsorted[i][0];
					m2[i-(l/2)][1] = unsorted[i][1];
				}
			}
			
			Msorted = merge_y(Msort_y(m1), Msort_y(m2));
			
			return Msorted;
		}
		
	}
	
	static int[][] merge_3(int[][] a, int[][] b) {
		int m = a.length;
		int n = b.length;
		int [][] c = new int[n+m][3];
		
		int j=0, k=0;
		while(j+k<m+n) {
			if(j>=m) {
				c[j+k][0] = b[k][0];
				c[j+k][1] = b[k][1];
				c[j+k][2] = b[k][2];
				k++;
			}
			else if(k>=n) {
				c[j+k][0] = a[j][0];
				c[j+k][1] = a[j][1];
				c[j+k][2] = a[j][2];
				j++;
			}
			else {
				if(a[j][0]<b[k][0]) {
					c[j+k][0] = a[j][0];
					c[j+k][1] = a[j][1];
					c[j+k][2] = a[j][2];
					j++;
				}
				else if(a[j][0]==b[k][0] && a[j][1]<b[k][1]) {
					c[j+k][0] = a[j][0];
					c[j+k][1] = a[j][1];
					c[j+k][2] = a[j][2];
					j++;
				}
				else {
					c[j+k][0] = b[k][0];
					c[j+k][1] = b[k][1];
					c[j+k][2] = b[k][2];
					k++;
				}
			}
		}
		return c;
	}
	
	
	
	static int[][] Msort_3(int[][] unsorted){
		int l = unsorted.length;
		
		if(l<=1) {
			return unsorted;
		}
		
		else {
			int[][] Msorted = new int[l][3];
			int[][] m1 = new int[l/2][3];
			int[][] m2 = new int[l-(l/2)][3];
			
			for(int i=0; i<l; i++) {
				if(i<l/2) {
					m1[i][0] = unsorted[i][0];
					m1[i][1] = unsorted[i][1];
					m1[i][2] = unsorted[i][2];
				}
				else {
					m2[i-(l/2)][0] = unsorted[i][0];
					m2[i-(l/2)][1] = unsorted[i][1];
					m2[i-(l/2)][2] = unsorted[i][2];
				}
			}
			
			Msorted = merge_3(Msort_3(m1), Msort_3(m2));
			
			return Msorted;
		}
		
	}

	public static void print2dArray(int [][] arr) {
		for(int i=0; i<arr.length; i++) {
			System.out.println(arr[i][0]+" "+arr[i][1]+" ");
		}
	}
		
    static boolean binarySearch(int arr[], int x, int y) 
    { 
        int l = 0, r = arr.length - 1; 
        while (l <= r) { 
            int m = l + (r - l) / 2; 
  
            // If x greater, ignore left half 
            if (arr[m] < x) 
                l = m + 1; 
  
            // If x is smaller, ignore right half 
            else if(arr[m] > y)
                r = m - 1; 
            
            else {
            	return true;
            }
        } 
  
        // if we reach here, then element was 
        // not present 
        return false; 
    } 
    
    static int gcd(int a, int b) 
    { 
        if (a == 0) 
            return b; 
        return gcd(b % a, a); 
    } 
  
	public static void main(String[] args) throws IOException {
		
		tmp = 0;
		count1 = 0;
		count2 = 0;
		
		ans = 0;
		
		Reader.init(System.in);
		
		OutputStream out = new BufferedOutputStream(System.out);
		
		int t = Reader.nextInt();
		
		for(int i=0; i<t; i++) {
			int n1  = Reader.nextInt();
			int a,b;
			tmp = 1;
			count1=1;
			ans = 1;
			a = Reader.nextInt();
			
			for(int j=1; j<n1; j++) {
				b = a;
				a = Reader.nextInt();
				if(a==b) {
					count1++;
				}
				else {
					if(ans<count1) {
						ans = count1;
					}
					count1 = 1;
				}	
			}
			if(ans<count1) {
				ans = count1;
			}
			out.write(Long.toString(ans).getBytes());
			out.write(("\n").getBytes());
		}
		out.flush();
		out.close();
		
	}
	
}