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
/*
        "Everything in the universe is balanced. Every disappointment
                you face in life will be balanced by something good for you!
                        Keep going, never give up."

*/


import java.util.*;
import java.lang.*;
import java.io.*;

public class Solution {
    /*
        Idea : 
        
            suppose we are at the ith index in our given array,
            and currently trying to form the jth segment, 
            since ...sumOfCurrentSegment(jth segment) < sumOfCurrentSegment((j - 1)th segment)... 
            here we would always try to maximize the sumOfCurrentSegment(j - 1)th segment, so that chances to form jth segment is maximized.
            
            That's what dp[i][j] stores.(The max sumOfCurrentSegment for a given segment)
        
    
    */
    
    public static void main(String[] args) throws java.lang.Exception {
        out = new PrintWriter(new BufferedOutputStream(System.out));
        sc = new FastReader();

        int test = sc.nextInt();
        for (int t = 0; t < test; t++) {
            solve();
        }
        out.close();
    }

    private static void solve() {
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        long[] prefix = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + arr[i];
        }

        // m is the max non-overlapping segments possible to form.
        int m = 1;
        while ((m + 1) * (m + 2) / 2 <= n) {
            m++;
        }
        
        // Let dp(i, j) be the maximal sumOfCurrentSegment on the segment of length j,
        // with that we have already considered all elements on the suffix i (that is, elements with indices i, i + 1,.. ..n)
        // and have already chosen segments with lengths j, j - 1,...1 in which the sums increase.
        long[][] dp = new long[n + 1][m + 1];
        for (int i = 0; i <= n; i++) {
            Arrays.fill(dp[i], -1);
        }
        dp[n][0] = Long.MAX_VALUE;
        for (int position = n - 1; position >= 0; position--) {
            for (int segment = 0; segment <= m; segment++) {
                // skip the current position
                dp[position][segment] = dp[position + 1][segment];

                // if we need to form some more segments on the suffix i.
                if (segment > 0) {
                    
                    // if its possible to form segment of length (segment), starting form position 
                    if (position + segment <= n) {
                        
                        // max sumOfCurrentSegment that we can have for the (j - 1)th segment
                        long sumOfCurrentSegment = prefix[position + segment] - prefix[position];
                        
                        // check if its possible to form rest of the segments, such that sumOfCurrentSegment(kth segment) < sumOfCurrentSegment((k - 1)th segment) < ... 1st segment 
                        if (sumOfCurrentSegment < dp[position + segment][segment - 1]) {
                            dp[position][segment] = Math.max(dp[position][segment], sumOfCurrentSegment);
                        }
                    }
                }
            }
        }

        // k is the max non-overlapping segments that can be formed.
        int k = 0;
        for (int i = 0; i <= m; i++) {
            if (dp[0][i] != -1) {
                k = i;
            }
        }
        out.println(k);
    }


    public static FastReader sc;
    public static PrintWriter out;
    static class FastReader
    {
        BufferedReader br;
        StringTokenizer str;

        public FastReader()
        {
            br = new BufferedReader(new
                    InputStreamReader(System.in));
        }

        String next()
        {
            while (str == null || !str.hasMoreElements())
            {
                try
                {
                    str = new StringTokenizer(br.readLine());
                }
                catch (IOException  end)
                {
                    end.printStackTrace();
                }
            }
            return str.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 end)
            {
                end.printStackTrace();
            }
            return str;
        }
    }
}