Description

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.

Input Format

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.

Output Format

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

3
7
24 20 20 12 6 6 22
10
10 7 2 3 5 6 4 13 21 30
5
2 3 4 5 6

3
6
2

Hint

Sample 1 Explanation

This sample describes the following code:

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