#include <bits/stdc++.h>

using namespace std;

#define optimizze() 		ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define watch(x) 		cout << (#x) << " is " << (x) << endl
#define ll				long long
#define yes				cout << "YES"<<"\n"
#define no				cout << "NO"<<"\n"
#define w(x)			int x; cin>>x; while(x--)
#define F 				first
#define S 				second
#define pb				push_back
#define all(x) 			x.begin(), x.end()


int main()
{
	optimizze();
	//.......................//

	w(t)
	{
		ll n;
		cin >> n;
		vector<ll> v(n);
		ll o = 0, tw = 0;
		for (int i = 0; i < n; ++i)
		{
			cin >> v[i];

		}
		vector<ll> sum(n, 0);
		for (int i = n - 1; i >= 0; --i)
		{
			o = 0;
			for (int j = i; j < n;)
			{
				if (sum[j])
				{
					o += sum[j];
					break;
				} else
				{
					o += v[j];
					j += v[j];
				}
			}
			sum[i] = o;
		}
		sort(all(sum));
		cout << sum.back() << endl;
	}

	return 0;
}


### Prompt

Please create a solution in cpp to the following problem:

Polycarp found under the Christmas tree an array a of n elements and instructions for playing with it: 

  * At first, choose index i (1 ≤ i ≤ n) — starting position in the array. Put the chip at the index i (on the value a_i). 
  * While i ≤ n, add a_i to your score and move the chip a_i positions to the right (i.e. replace i with i + a_i). 
  * If i > n, then Polycarp ends the game. 



For example, if n = 5 and a = [7, 3, 1, 2, 3], then the following game options are possible: 

  * Polycarp chooses i = 1. Game process: i = 1 \overset{+7}{\longrightarrow} 8. The score of the game is: a_1 = 7. 
  * Polycarp chooses i = 2. Game process: i = 2 \overset{+3}{\longrightarrow} 5 \overset{+3}{\longrightarrow} 8. The score of the game is: a_2 + a_5 = 6. 
  * Polycarp chooses i = 3. Game process: i = 3 \overset{+1}{\longrightarrow} 4 \overset{+2}{\longrightarrow} 6. The score of the game is: a_3 + a_4 = 3. 
  * Polycarp chooses i = 4. Game process: i = 4 \overset{+2}{\longrightarrow} 6. The score of the game is: a_4 = 2. 
  * Polycarp chooses i = 5. Game process: i = 5 \overset{+3}{\longrightarrow} 8. The score of the game is: a_5 = 3. 



Help Polycarp to find out the maximum score he can get if he chooses the starting index in an optimal way.

Input

The first line contains one integer t (1 ≤ t ≤ 10^4) — the number of test cases. Then t test cases follow.

The first line of each test case contains one integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the length of the array a.

The next line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 10^9) — elements of the array a.

It is guaranteed that the sum of n over all test cases does not exceed 2 ⋅ 10^5.

Output

For each test case, output on a separate line one number — the maximum score that Polycarp can get by playing the game on the corresponding array according to the instruction from the statement. Note that Polycarp chooses any starting position from 1 to n in such a way as to maximize his result.

Example

Input


4
5
7 3 1 2 3
3
2 1 4
6
2 1000 2 3 995 1
5
1 1 1 1 1


Output


7
6
1000
5

Note

The first test case is explained in the statement.

In the second test case, the maximum score can be achieved by choosing i = 1.

In the third test case, the maximum score can be achieved by choosing i = 2.

In the fourth test case, the maximum score can be achieved by choosing i = 1.

### Response

```cpp
#include <bits/stdc++.h>

using namespace std;

#define optimizze() 		ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define watch(x) 		cout << (#x) << " is " << (x) << endl
#define ll				long long
#define yes				cout << "YES"<<"\n"
#define no				cout << "NO"<<"\n"
#define w(x)			int x; cin>>x; while(x--)
#define F 				first
#define S 				second
#define pb				push_back
#define all(x) 			x.begin(), x.end()


int main()
{
	optimizze();
	//.......................//

	w(t)
	{
		ll n;
		cin >> n;
		vector<ll> v(n);
		ll o = 0, tw = 0;
		for (int i = 0; i < n; ++i)
		{
			cin >> v[i];

		}
		vector<ll> sum(n, 0);
		for (int i = n - 1; i >= 0; --i)
		{
			o = 0;
			for (int j = i; j < n;)
			{
				if (sum[j])
				{
					o += sum[j];
					break;
				} else
				{
					o += v[j];
					j += v[j];
				}
			}
			sum[i] = o;
		}
		sort(all(sum));
		cout << sum.back() << endl;
	}

	return 0;
}


```