Pchelyonok decided to give Mila a gift. Pchelenok has already bought an array a of length n, but gifting an array is too common. Instead of that, he decided to gift Mila the segments of that array!

Pchelyonok wants his gift to be beautiful, so he decided to choose k non-overlapping segments of the array [l_1,r_1], [l_2,r_2], … [l_k,r_k] such that:

  * the length of the first segment [l_1,r_1] is k, the length of the second segment [l_2,r_2] is k-1, …, the length of the k-th segment [l_k,r_k] is 1 
  * for each i<j, the i-th segment occurs in the array earlier than the j-th (i.e. r_i<l_j) 
  * the sums in these segments are strictly increasing (i.e. let sum(l … r) = ∑_{i=l}^{r} a_i — the sum of numbers in the segment [l,r] of the array, then sum(l_1 … r_1) < sum(l_2 … r_2) < … < sum(l_k … r_k)). 



Pchelenok also wants his gift to be as beautiful as possible, so he asks you to find the maximal value of k such that he can give Mila a gift!

Input

The first line contains a single integer t (1 ≤ t ≤ 100) — the number of test cases. The next 2 ⋅ t lines contain the descriptions of test cases. The description of each test case consists of two lines.

The first line of each test case contains a single integer n (1 ≤ n ≤ 10^5) — the length of the array.

The second line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 10^9) — the elements of the array a.

It is guaranteed that the sum of n over all test cases does not exceed 10^5.

Output

For each test case, print the maximum possible value of k.

Example

Input


5
1
1
3
1 2 3
5
1 1 2 2 3
7
1 2 1 1 3 2 6
5
9 6 7 9 7


Output


1
1
2
3
1
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStreamWriter;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Map.Entry;


import java.util.Random;
import java.util.TreeSet;

public final class CF_750_D2_E3
{


	static boolean verb=true;
	static void log(Object X){if (verb) System.err.println(X);}
	static void log(Object[] X){if (verb) {for (Object U:X) System.err.print(U+" ");System.err.println("");}}
	static void log(int[] X){if (verb) {for (int U:X) System.err.print(U+" ");System.err.println("");}}
	static void logWln(int[] X){if (verb) {for (int U:X) System.err.print(U+" ");}}
	static void log(int[] X,int L){if (verb) {for (int i=0;i<L;i++) System.err.print(X[i]+" ");System.err.println("");}}
	static void log(long[] X){if (verb) {for (long U:X) System.err.print(U+" ");System.err.println("");}}

	static void logWln(Object X){if (verb) System.err.print(X);}
	static void info(Object o){	System.out.println(o);}
	static void output(Object o){outputWln(""+o+"\n");	}
	static void outputFlush(Object o){try {out.write(""+ o+"\n");out.flush();} catch (Exception e) {}}
	static void outputWln(Object o){try {out.write(""+ o);} catch (Exception e) {}}


	static void logBin(int[] tm) {for (int x:tm) logWln(bin(8,x)+" ");log("");}

	static String bin(int L,int x) {
		String s=Integer.toBinaryString(x);
		while (s.length()<L) s="0"+s;
		return s;
	}

	// Global vars
	static BufferedWriter out;
	static InputReader reader;


	static void test() {
		log("testing");

		Random r=new Random();
		int NTESTS=10000000;
		int NMAX=10;
		int VMAX=1;
		for (int t=0;t<NTESTS;t++) {
			int n=r.nextInt(NMAX)+2;


		}
		log("testing done");

	}



	static int MX=Integer.MAX_VALUE;


	// this does not prevent some zero


	static int[][] perm= {{0,1,2},{0,2,1},{1,2,0}};


	static final int convert(int a,int b,int c) {
		return a*c+b;
	}


	static void process() throws Exception {

		//log("hello");
		//test2();
		//test();
		out = new BufferedWriter(new OutputStreamWriter(System.out));
		reader = new InputReader(System.in);

		int T=reader.readInt();
		for (int t=0;t<T;t++) {
			int n=reader.readInt();

			long[] km=new long[n];
			long cur=1;
			km[0]=cur;


			for (int i=1;i<n;i++) {
				if (((cur+1)*(cur+2))<=2*(i+1)) {
					cur++;
				}
				km[i]=cur;
			}
			////log(km);

			long[] a=new long[n];
			for (int i=0;i<n;i++) {
				a[n-1-i]=reader.readInt();
			}

			long[] sum=new long[n];
			sum[0]=a[0];
			for (int i=1;i<n;i++) {
				sum[i]=sum[i-1];
				sum[i]+=a[i];
			}

			//log("sum");
			//log(sum);
			int KX=(int)km[n-1]+2;
			long[] mx=new long[KX];
			mx[0]=Long.MAX_VALUE;
			mx[1]=a[0];
			int[] update=new int[n*KX];
			
			for (int i=1;i<n;i++) {
				int mox=(int)(Math.min(km[n-1],n-i));
				//log("mox:"+mox);
				for (int k=1;k<=mox;k++) {
					//log("contemplating k:"+k);
					// we can consider doing k at i
					long sm=sum[i+k-1];
					if (i>0)
						sm-=sum[i-1];
					// now we look at all the previous ones that are bigger
					// if they exist, we are ok
					//log("sm:"+sm);

					if (mx[k-1]>sm) {
						//log("ok :"+mx[k-1]);
						int w=convert(i+k-1,k,KX);
						update[w]=Math.max(update[w],(int)sm);
		
					} else
						break;

				}
				for (int k=1;k<KX+1;k++) {
					mx[k]=Math.max(mx[k],update[convert(i,k,KX)]);
					if (mx[k]==0)
						break;
				}
			}
			int target=1;

			for (int k=0;k<KX;k++) {
				if (mx[k]!=0)
					target=k;
			}
			output(target);

		}

		try {
			out.close();
		} catch (Exception Ex) {
		}


	}





	public static void main(String[] args) throws Exception {
		process();

	}

	static final class InputReader {
		private final InputStream stream;
		private final byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public InputReader(InputStream stream) {
			this.stream = stream;
		}

		private int read() throws IOException {
			if (curChar >= numChars) {
				curChar = 0;
				numChars = stream.read(buf);
				if (numChars <= 0) {
					return -1;
				}
			}
			return buf[curChar++];
		}

		public final String readString() throws IOException {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			StringBuilder res = new StringBuilder();
			do {
				res.append((char) c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public final String readString(int L) throws IOException {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			StringBuilder res = new StringBuilder(L);
			do {
				res.append((char) c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public final int readInt() throws IOException {
			int c = read();
			boolean neg = false;
			while (isSpaceChar(c)) {
				c = read();
			}
			char d = (char) c;
			// log("d:"+d);
			if (d == '-') {
				neg = true;
				c = read();
			}
			int res = 0;
			do {
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			// log("res:"+res);
			if (neg)
				return -res;
			return res;

		}

		public final long readLong() throws IOException {
			int c = read();
			boolean neg = false;
			while (isSpaceChar(c)) {
				c = read();
			}
			char d = (char) c;
			// log("d:"+d);
			if (d == '-') {
				neg = true;
				c = read();
			}
			long res = 0;
			do {
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			// log("res:"+res);
			if (neg)
				return -res;
			return res;

		}

		private boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
	}

}
