#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1e9+5
#define mod 1000000007
#define forn(i,n) for (int i = 0; i < n; i++)
#define deb(x) cout << #x << "=" << x << endl 
#define deb2(x,y) cout << #x << "=" << x << ", " << #y << "=" << y << endl 
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define PI 3.1415926535897932384626
#define setbits(x) __builtin_popcount(x)
#define gcd(a,b) __gcd(a,b)
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pi> vpi;


void solve(){
    int n; cin>>n;
    vl arr(n);
    forn(i,n)cin>>arr[i];
    ll maxi=-1;
    for(ll i=n-1;i>=0;i--){
        if(arr[i]+i<n){
            arr[i]+=arr[i+arr[i]];
        }
        maxi=max(maxi,arr[i]);
    }
    cout<<maxi<<"\n";
    
}    

int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin>>t;
    while(t--){
       solve();
    }

}
### Prompt

Construct a cpp code solution to the problem outlined:

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;
typedef long long ll;
#define INF 1e9+5
#define mod 1000000007
#define forn(i,n) for (int i = 0; i < n; i++)
#define deb(x) cout << #x << "=" << x << endl 
#define deb2(x,y) cout << #x << "=" << x << ", " << #y << "=" << y << endl 
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define PI 3.1415926535897932384626
#define setbits(x) __builtin_popcount(x)
#define gcd(a,b) __gcd(a,b)
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pi> vpi;


void solve(){
    int n; cin>>n;
    vl arr(n);
    forn(i,n)cin>>arr[i];
    ll maxi=-1;
    for(ll i=n-1;i>=0;i--){
        if(arr[i]+i<n){
            arr[i]+=arr[i+arr[i]];
        }
        maxi=max(maxi,arr[i]);
    }
    cout<<maxi<<"\n";
    
}    

int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin>>t;
    while(t--){
       solve();
    }

}
```