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
/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
public class Codechef
{static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    } 
//    static int mod = 998244353 ;
//    static int N = 200005;
//    static long factorial_num_inv[] = new long[N+1];
//    static long natual_num_inv[] = new long[N+1];
//    static long fact[] = new long[N+1];
//    static void InverseofNumber() 
//{ 
//    natual_num_inv[0] = 1;
//    natual_num_inv[1] = 1; 
//    for (int i = 2; i <= N; i++) 
//        natual_num_inv[i] = natual_num_inv[mod % i] * (mod - mod / i) % mod; 
//} 
//static void InverseofFactorial() 
//{ 
//    factorial_num_inv[0] = factorial_num_inv[1] = 1; 
  
//    for (int i = 2; i <= N; i++) 
//        factorial_num_inv[i] = (natual_num_inv[i] * factorial_num_inv[i - 1]) % mod; 
//} 
//static long nCrModP(long N, long R) 
//{ 
//    long ans = ((fact[(int)N] * factorial_num_inv[(int)R]) % mod * factorial_num_inv[(int)(N - R)]) % mod; 
//    return ans%mod; 
//}
    //static boolean prime[];
    //static void sieveOfEratosthenes(int n)
    //{
    //    prime = new boolean[n+1];
        
    //    for (int i = 0; i <= n; i++)
    //        prime[i] = true;
 
    //    for (int p = 2; p * p <= n; p++)
    //    {
    //        // If prime[p] is not changed, then it is a
    //        // prime
    //        if (prime[p] == true)
    //        {
    //            // Update all multiples of p
    //            for (int i = p * p; i <= n; i += p)
    //                prime[i] = false;
    //        }
    //    }
 
        
    //}
    
	public static void main (String[] args) throws java.lang.Exception
	{
    //    InverseofNumber();
    //    InverseofFactorial();
    //   fact[0] = 1; 
    //   for (long i = 1; i <= 2*100000; i++)
    //   { 
    //       fact[(int)i] = (fact[(int)i - 1] * i) % mod; 
    //   }
    
		FastReader scan = new FastReader();
		PrintWriter pw = new PrintWriter(System.out);
        int t = scan.nextInt();
        while(t-->0){
            int n = scan.nextInt();
            long a[] = new long[n+1];
            long prefix[] = new long[n+1];
            for(int i=1;i<=n;i++){
                a[i] = scan.nextLong();
                prefix[i] = a[i]+prefix[i-1];
            }
            long dp[][] = new long[n+2][452];
            for(int i=0;i<=n+1;i++){
                for(int j=0;j<452;j++){
                    dp[i][j] = Integer.MIN_VALUE;
                }
            }
            long max = 10000000000000000L;
            dp[n+1][0] = max;
            for(int i=n;i>=1;i--){
                dp[i][0] = max;
                for(int j=1;j<452;j++){
                    if(i+j>n+1) continue;
                    if(prefix[i+j-1]-prefix[i-1]<dp[i+j][j-1]){
                        dp[i][j] = prefix[i+j-1]-prefix[i-1];
                    }
                    dp[i][j] = Math.max(dp[i][j],dp[i+1][j]);
                }
            }
            int ans = 0;
            for(int i=1;i<451;i++){
                if(dp[1][i]>0)
                ans = i;
            }
            pw.println(ans);
            pw.flush();
        }
    }
    
//   static long gcd(long a,long b){
//       if(a==0)
//       return b;
//       return gcd(b%a,a);
//   }
//   static long lcm(long a,long b){
//       return (a/gcd(a,b))*b;
//   }
}
//class Pair{
//    Integer x,y;
//    Pair(int x,int y){
//        this.x = x;
//        this.y = y;
//    }
//    public boolean equals(Object obj) {
//        // TODO Auto-generated method stub
//        if(obj instanceof Pair)
//        {
//            Pair temp = (Pair) obj;
//            if(this.x.equals(temp.x) && this.y.equals(temp.y))
//                return true;
//        }
//        return false;
//    }

//    @Override
//    public int hashCode() {
//        // TODO Auto-generated method stub
        
//        return (this.x.hashCode() + this.y.hashCode());        
//    }
//}
//class Compar implements Comparator<Pair>{
//    public int compare(Pair p1,Pair p2){
//        return p1.x-p2.x;
//    }
//}
