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
// notice the ""
#include "bits/stdc++.h"

using namespace std;

#define log1(x) cout << #x << ": " << x << endl
#define log2(x, y) cout << #x << ": " << x << ", " << #y << ": " << y << endl

#define rep(i, x, n) for (ll i = x; i < n; i++)
#define repb(i, x, n) for (ll i = x; i >= n; i--)
#define nl "\n"
#define YES cout << "YES\n";
#define NO cout << "NO\n";
#define Yes cout << "Yes\n";
#define No cout << "No\n";

typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
typedef priority_queue<ll, vll, greater<ll>> minpq;
typedef priority_queue<ll> maxpq;

// clang-format off
template <typename T> void _log(const T &t) { cout << t << " "; }
template <typename T, typename U> void _log(const pair<T, U> &p) {_log(p.first); cout<<": "; _log(p.second);cout<<endl;}
template <typename T> void _log(const vector<T> &v) {for (const T &t : v) _log(t); cout << endl;}
template <typename T> void _log(const vector<vector<T>> &v) {for (const vector<T> &t : v) _log(t); cout << endl;}
template <typename T> void _log(const unordered_set<T> &s) {for (const T &t : s) _log(t); cout << nl;}
template <typename T> void _log(const set<T> &s) {for (const T &t : s) _log(t);cout << nl;}
template <typename T> void _log(const multiset<T> &s) {for (const T &t : s) _log(t);cout << nl;}
template <typename T, typename U> void _log(const map<T, U> &m) {for (const pair<T, U> t : m) {_log(t);}}
template <typename T, typename U> void _log(const unordered_map<T, U> &m) {for (const pair<T, U> t : m) {_log(t);}}
/* const long long MOD = 998244353; */
const long long MOD = 1e9 + 7;
const long long LINF = numeric_limits<long long>::max();
const int INF = numeric_limits<int>::max();
long long _ceiling(long long a, long long b) { return (a + b - 1) / b; } // ceil a/b
long long _MOD(long long a) { return (a + MOD) % MOD; }
long long _pow(long long a, long long b) {long long res = 1; a = _MOD(a); while (b) {if (b % 2) res = _MOD(res * a); a = _MOD(a * a); b = b / 2;}return res;}
long long _inverse(long long a) { return _pow(_MOD(a), MOD - 2); } // euler phi for primes is p - 1
long long _inversemod(long long a, long long p) { return _pow(a, p - 2); } // euler phi for primes is p - 1
long long _lcm(long long a, long long b) { return (a * b) / __gcd(a, b); }
// clang-format on

// fixed size vector? use array<int, n>
#define MAXSEG 446

void solve() {
  int n;
  cin >> n;
  vi a(n);
  for (auto &e : a)
    cin >> e;

  vector<int> pfxsum(n);
  pfxsum[0] = a[0];
  rep(i, 1, n) pfxsum[i] = pfxsum[i - 1] + a[i];

  auto rangesum = [&](int l, int r) {
    return pfxsum[r] - (l - 1 >= 0 ? pfxsum[l - 1] : 0);
  };

  vector<vector<int>> dp(n, vector<int>(MAXSEG + 1, -1));
  dp[n - 1][1] = a[n - 1];
  rep(i, 0, n) { dp[i][0] = INF; }

  for (int i = n - 2; i >= 0; i--) {
    for (int j = 1; j <= MAXSEG; j++) {
      int x = dp[i + 1][j];
      int y = -1;
      if (i + j < n) {
        int rs = rangesum(i, i + j - 1);
        if (rs >= dp[i + j][j - 1])
          y = -1;
        else
          y = rs;
      }

      dp[i][j] = max(x, y);
    }
  }

  /* _log(dp); */

  for (int i = MAXSEG; i > 0; i--) {
    if (dp[0][i] != -1) {
      cout << i << nl;
      return;
    }
  }
}

int main() {
#ifdef ichigo_runtime
  auto start = std::chrono::high_resolution_clock::now();
#endif

  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int t = 1;
  cin >> t;

  while (t--) {
    solve();
  }

#ifdef ichigo_runtime
  auto stop = std::chrono::high_resolution_clock::now();
  auto duration =
      chrono::duration_cast<chrono::milliseconds>(stop - start).count();
  cout << "Execution Time: " << duration << "ms" << nl;
#endif
}
