题目描述

Polycarp 在圣诞树下发现了一个长度为 $n$ 的数组 $a$，以及一份关于如何玩这个数组的说明：

• 首先，选择一个下标 $i$（$1 \leq i \leq n$）作为数组的起始位置。将棋子放在下标 $i$（即 $a_i$ 的位置）。
• 只要 $i \leq n$，就将 $a_i$ 加到你的得分上，并将棋子向右移动 $a_i$ 个位置（即将 $i$ 替换为 $i + a_i$）。
• 如果 $i > n$，那么 Polycarp 就结束游戏。

例如，如果 $n = 5$ 且 $a = [7, 3, 1, 2, 3]$，则可能的游戏过程如下：

• Polycarp 选择 $i = 1$。游戏过程：$i = 1 \overset{+7}{\longrightarrow} 8$。游戏得分为：$a_1 = 7$。
• Polycarp 选择 $i = 2$。游戏过程：$i = 2 \overset{+3}{\longrightarrow} 5 \overset{+3}{\longrightarrow} 8$。游戏得分为：$a_2 + a_5 = 6$。
• Polycarp 选择 $i = 3$。游戏过程：$i = 3 \overset{+1}{\longrightarrow} 4 \overset{+2}{\longrightarrow} 6$。游戏得分为：$a_3 + a_4 = 3$。
• Polycarp 选择 $i = 4$。游戏过程：$i = 4 \overset{+2}{\longrightarrow} 6$。游戏得分为：$a_4 = 2$。
• Polycarp 选择 $i = 5$。游戏过程：$i = 5 \overset{+3}{\longrightarrow} 8$。游戏得分为：$a_5 = 3$。

请你帮助 Polycarp 找出，如果他以最优方式选择起始下标，最多能获得多少分。

输入格式

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。接下来有 $t$ 组测试用例。

每组测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2 \times 10^5$），表示数组 $a$ 的长度。

下一行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^9$），表示数组 $a$ 的元素。

保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

输出格式

对于每个测试用例，输出一行一个整数，表示 Polycarp 按照题目描述的规则，在对应数组上玩游戏时能够获得的最大得分。注意，Polycarp 可以从 $1$ 到 $n$ 的任意起始位置选择，以使得得分最大。

说明/提示

第一个测试用例的解释见题面。

在第二个测试用例中，最大得分可以通过选择 $i = 1$ 获得。

在第三个测试用例中，最大得分可以通过选择 $i = 2$ 获得。

在第四个测试用例中，最大得分可以通过选择 $i = 1$ 获得。

由 ChatGPT 4.1 翻译

样例

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

7
6
1000
5