P14576 Lamborghini (Remix)

> _Blue flames swirling, controlling my speed_ > _Game started, eyes lock, then I proceed_ > _The industry's dark side, it's dangerous to roam_ > _Gotta keep my balance, never slip, stay in control_ > — _Lamborghini (Hurricane is Coming)_ [P10795『SpOI - R1』Lamborghini (Demo)](https://www.luogu.com.cn/problem/P10795).

The **cursor** is an indicator that can appear between two adjacent characters in a line of code, at the end of a line of code, or at the beginning of a line of code. For example, as shown in the figure below:  These three vertical lines represent the cursors. In modern code editors, we can typically place multiple cursors at the same time. When the left arrow key is pressed, all cursors will **simultaneously** move one character to the left. Specifically, the cursor at the beginning of the current line will move to the end of the previous line, and the cursor at the beginning of the first line will disappear. When the right arrow key is pressed, all cursors will **simultaneously** move one character to the right. Specifically, the cursor at the end of the current line will move to the beginning of the next line, and the cursor at the end of the last line will disappear. ----------- Now, Simons has a piece of code with $n$ lines. The length of the $i$-th line is $a_i$ (i.e., the $i$-th line is a string of length $a_i$). Simons wants to know the maximum number of cursors that can be placed in the same line after pressing the arrow keys multiple times, assuming that he initially places the cursors at the ends of some lines. You only need to output this maximum value.

**Each test contains multiple test cases.** For each test: The first line contains an integer $T$, representing the number of test cases. For each test case: The first line contains an integer $n$, representing the number of lines of code. The next line contains $n$ integers separated by spaces, where the $i$-th integer $a_i$ represents the length of the code in the $i$-th line.

For each test case, output a single integer on one line, representing the answer.

### Sample 1 Explanation This sample describes the following code: ```cpp #include #define ll long long using namespace std; int pi=3.14; int a; int b; #define ld long double ``` Clearly, the lengths of the lines of code are as follows: $24,20,20,12,6,6,22$. Simons can place cursors at the end of lines $4,5,6$:  By repeatedly pressing the left arrow key, these $3$ cursors can all appear simultaneously in the second line:  Alternatively, by repeatedly pressing the right arrow key, these $3$ cursors can all appear simultaneously in the seventh line:  It can be proven that there is no way to place more cursors on the same line. ### Data Range For $100\%$ of the data, the constraints are: $1\le T\le 10$, $1 \le n \le 2\times 10^5$, and $1 \le a_i \le 10^9$. |Subtask|$n \le$|Special Properties|Score| |:-:|:-:|:-:|:-:| |Subtask 1|$20$|None|$20$| |Subtask 2|$200$|None|$20$| |Subtask 3|$5000$|None|$20$| |Subtask 4|$2 \times 10^4$|$a_i \le 1000$|$20$| |Subtask 5|$2 \times 10^5$|None|$20$|