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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.text.DecimalFormat;
import java.util.*;
import java.util.concurrent.ThreadLocalRandom;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.LongStream;

public class TaskB {

    static long mod = 1000000007;
    static FastScanner scanner;

    static final StringBuilder result = new StringBuilder();

    public static void main(String[] args) {
        scanner = new FastScanner();
        int T = scanner.nextInt();
        for (int t = 0; t < T; t++) {
            solve();
            result.append("\n");
        }
        System.out.println(result);
    }

    // a * x + b * y = 0
    // x = -b * y / a

    // y = a
    // x = -b

    static void solve() {
        int n = scanner.nextInt();
        int maxK = (int) (2 * Math.sqrt(n + 1)) + 1;
        int[] a = scanner.nextIntArray(n);
        int[][] dp = new int[n][maxK];
        dp[n - 1][1] = a[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            dp[i][1] = Math.max(a[i], dp[i + 1][1]);
            int sum = a[i];
            for (int k = 2; k < maxK; k++) {
                if (i + k >= n) break;
                sum += a[i + k - 1];
                if (sum < 0) break;
                if (dp[i + k][k - 1] == 0) break;
                dp[i][k] = sum < dp[i + k][k - 1] ? sum : 0;
                dp[i][k] = Math.max(dp[i][k], dp[i + 1][k]);
            }
        }
        for (int i = maxK - 1; i >= 1; i--) {
            if (dp[0][i] != 0) {
                result.append(i);
                return;
            }
        }
    }


    static class WithIdx implements Comparable<WithIdx> {
        int val, idx;

        public WithIdx(int val, int idx) {
            this.val = val;
            this.idx = idx;
        }

        @Override
        public int compareTo(WithIdx o) {
            if (val == o.val) {
                return Integer.compare(idx, o.idx);
            }
            return Integer.compare(val, o.val);
        }
    }

    public static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

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

        String nextToken() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    // TODO Auto-generated catch block
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        String nextLine() {
            try {
                return br.readLine();
            } catch (Exception e) {
                e.printStackTrace();
                throw new RuntimeException();
            }
        }

        int nextInt() {
            return Integer.parseInt(nextToken());
        }

        long nextLong() {
            return Long.parseLong(nextToken());
        }

        double nextDouble() {
            return Double.parseDouble(nextToken());
        }

        int[] nextIntArray(int n) {
            int[] res = new int[n];
            for (int i = 0; i < n; i++) res[i] = nextInt();
            return res;
        }

        long[] nextLongArray(int n) {
            long[] res = new long[n];
            for (int i = 0; i < n; i++) res[i] = nextLong();
            return res;
        }

        String[] nextStringArray(int n) {
            String[] res = new String[n];
            for (int i = 0; i < n; i++) res[i] = nextToken();
            return res;
        }
    }

    static class PrefixSums {
        long[] sums;

        public PrefixSums(long[] sums) {
            this.sums = sums;
        }

        public long sum(int fromInclusive, int toExclusive) {
            if (fromInclusive > toExclusive) throw new IllegalArgumentException("Wrong value");
            return sums[toExclusive] - sums[fromInclusive];
        }

        public static PrefixSums of(int[] ar) {
            long[] sums = new long[ar.length + 1];
            for (int i = 1; i <= ar.length; i++) {
                sums[i] = sums[i - 1] + ar[i - 1];
            }
            return new PrefixSums(sums);
        }

        public static PrefixSums of(long[] ar) {
            long[] sums = new long[ar.length + 1];
            for (int i = 1; i <= ar.length; i++) {
                sums[i] = sums[i - 1] + ar[i - 1];
            }
            return new PrefixSums(sums);
        }
    }

    static class ADUtils {
        static void sort(int[] ar) {
            Random rnd = ThreadLocalRandom.current();
            for (int i = ar.length - 1; i > 0; i--) {
                int index = rnd.nextInt(i + 1);
                // Simple swap
                int a = ar[index];
                ar[index] = ar[i];
                ar[i] = a;
            }
            Arrays.sort(ar);
        }

        static void reverse(int[] arr) {
            int last = arr.length / 2;
            for (int i = 0; i < last; i++) {
                int tmp = arr[i];
                arr[i] = arr[arr.length - 1 - i];
                arr[arr.length - 1 - i] = tmp;
            }
        }

        static void sort(long[] ar) {
            Random rnd = ThreadLocalRandom.current();
            for (int i = ar.length - 1; i > 0; i--) {
                int index = rnd.nextInt(i + 1);
                // Simple swap
                long a = ar[index];
                ar[index] = ar[i];
                ar[i] = a;
            }
            Arrays.sort(ar);
        }
    }

    static class MathUtils {
        static long[] FIRST_PRIMES = {
                2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
                31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
                73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
                127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
                179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
                233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
                283, 293, 307, 311, 313, 317, 331, 337, 347, 349,
                353, 359, 367, 373, 379, 383, 389, 397, 401, 409,
                419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
                467, 479, 487, 491, 499, 503, 509, 521, 523, 541,
                547, 557, 563, 569, 571, 577, 587, 593, 599, 601,
                607, 613, 617, 619, 631, 641, 643, 647, 653, 659,
                661, 673, 677, 683, 691, 701, 709, 719, 727, 733,
                739, 743, 751, 757, 761, 769, 773, 787, 797, 809,
                811, 821, 823, 827, 829, 839, 853, 857, 859, 863,
                877, 881, 883, 887, 907, 911, 919, 929, 937, 941,
                947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013,
                1019, 1021, 1031, 1033, 1039, 1049, 1051};

        static long[] primes(int to) {
            long[] all = new long[to + 1];
            long[] primes = new long[to + 1];
            all[1] = 1;
            int primesLength = 0;
            for (int i = 2; i <= to; i++) {
                if (all[i] == 0) {
                    primes[primesLength++] = i;
                    all[i] = i;
                }
                for (int j = 0; j < primesLength && i * primes[j] <= to && all[i] >= primes[j];
                        j++) {
                    all[(int) (i * primes[j])] = primes[j];
                }
            }
            return Arrays.copyOf(primes, primesLength);
        }

        static long modpow(long b, long e, long m) {
            long result = 1;

            while (e > 0) {
                if ((e & 1) == 1) {
                    /* multiply in this bit's contribution while using modulus to keep
                     * result small */
                    result = (result * b) % m;
                }
                b = (b * b) % m;
                e >>= 1;
            }

            return result;
        }

        static long submod(long x, long y, long m) {
            return (x - y + m) % m;
        }

        static long modInverse(long a, long m) {
            long g = gcdF(a, m);
            if (g != 1) {
                throw new IllegalArgumentException("Inverse doesn't exist");
            } else {
                // If a and m are relatively prime, then modulo
                // inverse is a^(m-2) mode m
                return modpow(a, m - 2, m);
            }
        }

        static public long gcdF(long a, long b) {
            while (b != 0) {
                long na = b;
                long nb = a % b;
                a = na;
                b = nb;
            }
            return a;
        }
    }
}

/*
5
3 2 3 8 8
2 8 5 10 1

 */