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.*;
import java.util.*;

public class E {
    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 FastReader s = new FastReader();
    static PrintWriter out = new PrintWriter(System.out);

    private static int[] rai(int n) {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = s.nextInt();
        }
        return arr;
    }

    private static int[][] rai(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] = s.nextInt();
            }
        }
        return arr;
    }

    private static long[] ral(int n) {
        long[] arr = new long[n];
        for (int i = 0; i < n; i++) {
            arr[i] = s.nextLong();
        }
        return arr;
    }

    private static long[][] ral(int n, int m) {
        long[][] arr = new long[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                arr[i][j] = s.nextLong();
            }
        }
        return arr;
    }

    private static int ri() {
        return s.nextInt();
    }

    private static long rl() {
        return s.nextLong();
    }

    private static String rs() {
        return s.next();
    }

    static long gcd(long a,long b)
    {
        if(b==0)
        {
            return a;
        }
        return gcd(b,a%b);
    }

    static int gcd(int a,int b)
    {
        if(b==0)
        {
            return a;
        }
        return gcd(b,a%b);
    }

    static boolean isPrime(int n) {
        //check if n is a multiple of 2
        if (n % 2 == 0) return false;
        //if not, then just check the odds
        for (int i = 3; i <= Math.sqrt(n); i += 2) {
            if (n % i == 0)
                return false;
        }
        return true;
    }
    static int MOD=1000000007;

    static long mpow(long base,long pow)
    {
        long res=1;
        while(pow>0)
        {
            if(pow%2==1)
            {
                res=(res*base)%MOD;
            }
            pow>>=1;
            base=(base*base)%MOD;
        }
        return res;
    }

    static enum Type
    {
        T1, T2,T3, T4
    }


    static class Node
    {
        String start,end;
        long count;
        long len ;

        public Node(String start, String end, long count, long len) {
            this.start = start;
            this.end = end;
            this.count = count;
            this.len = len;
        }

        @Override
        public String toString() {
            return "("+start+" "+end+" "+count+")";
        }
    }

    public static void main(String[] args) {
        StringBuilder ans = new StringBuilder();
        int t = ri();
//        int t = 1;
//        int tc = 0;
        while (t-- > 0)
        {
            int n=ri();
            long[] arr=ral(n);
            long[] prefSum = new long[n];
            long currSum =0;
            for(int i=0;i<n;i++)
            {
                currSum+=arr[i];
                prefSum[i]=currSum;
            }

//            int x=1;
//            while(true)
//            {
//                int sum = (x*(x+1))/2;
//                if(sum>n)
//                {
//                    x-=1;
//                    break;
//                }
//                x++;
//            }

            int k = 1;

            long[] prev = new long[n];
            prev[n-1]=arr[n-1];

            for(int i=n-2;i>=0;i--)
            {
                prev[i] = Math.max(arr[i],prev[i+1]);
            }

            int sum = k;

            long[] curr = new long[n];
            while(true)
            {
//                System.out.println(Arrays.toString(prev));
                boolean has = false;
                k++;
                sum+=k;
                for (int i = n - sum; i >= 0; i--) {
                    currSum = prefSum[i+k-1];
                    if(i>0)
                    {
                        currSum-=prefSum[i-1];
                    }

                    if(prev[i+k]>currSum)
                    {
                        has = true;
                        curr[i]=Math.max(curr[i+1],currSum);
                    }


                }

                if(!has)
                {
                    break;
                }

                prev=curr;
                curr=new long[n];
            }

            ans.append(k-1).append("\n");


        }
        out.print(ans.toString());
        out.flush();
    }



}