题目描述

给定一个长度为 $n$ 的数组 $a$，初始只有 $a_1$ 是已被解锁的。现在有一个整数 $i$，初始值为 $1$。现在$kkkw$ 在对这个数组进行一个游戏：

• 如果 $a_i$ 未被解锁，游戏结束。
• 否则他可以将 $a_{i+1\sim i+a_i}$ 设置成已被解锁的，或是获得 $a_i$ 个金币（如果 $a_i=0$ 则无法解锁任何元素），然后将 $i$ 加 $1$。

请你求出游戏结束后你能获得的最大金币数量。

输入格式

本题有多组测试数据。

第一行一个整数 $T$，表示测试数据组数。

对于每一组数据，第一行一个正整数 $n$。

接下来一行 $n$ 个非负整数 $a_{1\sim n}$。

输出格式

对于每一组数据，一行一个数，表示答案。

3
2
1 2
5
2 4 5 0 1
4
0 4 4 4

2
9
0

1
10
1 1 4 5 1 4 1 9 1 9

26

说明/提示

【样例 1 解释】

对于第一组数据，你可以解锁 $a_2$，再获得 $a_2$ 个金币。而对于第三组数据，你无法解锁 $a_2$，因此只能获得 $0$ 个金币。

对于第二组数据，你可以解锁 $a_2,a_3$，并获得 $9$ 个金币。

【样例 2 解释】

将第 $1,2,3,6$ 个位置用于解锁为最优方案。

【数据范围】

对于 $100\%$ 的数据，$1\le n\le10^5$，$0\le a_i\le10^5$，$T\le 5$。