Snackdown 2019 is coming! People have started to spread the word and tell other people about the contest.
There are $N$ people numbered $1$ through $N$. Initially, only person $1$ knows about Snackdown. On each day, everyone who already knows about Snackdown tells other people about it. For each valid $i$, person $i$ can tell up to $A_i$ people per day. People spread the information among the people who don't know about Snackdown in the ascending order of their indices; you may assume that no two people try to tell someone about Snackdown at the same moment. Each person is only allowed to start telling other people about Snackdown since the day after he/she gets to know about it (person $1$ can start telling other people already on day $1$). How many days does it take for all people to know about Snackdown?

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains a single integer $N$.
- The second line contains $N$ space-separated integers $A_1, A_2, \dots, A_N$.

-----Output-----
For each test case, print a single line containing one integer — the number of days.

-----Constraints-----
- $1 \le T \le 1,000$
- $2 \le N \le 10^5$
- the sum of $N$ for all test cases does not exceed $10^6$
- $0 \le A_i \le N$ for each valid $i$
- $1 \le A_1$

-----Example Input-----
2
7
2 1 1 5 5 5 5
5
5 1 3 2 1

-----Example Output-----
2
1

-----Explanation-----
Example case 1: On day $1$, person $1$ tells people $2$ and $3$ about Snackdown. On day $2$, the first three people know about Snackdown, so they can tell $2+1+1 = 4$ people about it in a single day. That means the last four people get to know about Snackdown on day $2$, so the total number of days is $2$.
Example case 2: On each day, person $1$ can tell up to $5$ people about Snackdown, so on the first day, he simply tells all people about it and the total number of days is $1$.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'try:\n for i in range(int(input())):\n  n=int(input())\n  b=input()\n  b=b.split()\n  b=list(map(int,b))\n  day=0\n  t=list(map(int,b))\n  t[0]=-1\n  tell=b[0]\n  known=1\n  q=[-1 for i in range(n)]\n  for i in range(1,n):\n   if t[i]!=-1:\n    p=0\n    c=0\n    if tell>n-known:\n     for j in range(i,n):\n      t[j]=-1\n      known+=1\n      p+=1\n      c+=b[j]\n     day+=1\n     tell+=c\n    else:\n     for j in range(i,i+tell):\n      t[j]=-1\n      known+=1\n      p+=1\n      c+=b[j]\n     day+=1\n     tell+=c\n    if t==q:\n     break\n  print(day)\n\nexcept:\n None\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13403