背景

在编程王国，每年都会举办一场盛大的编程赛事——“匹配之道”大赛。这个比赛吸引了无数程序员前来参加，挑战他们的算法与优化能力。在比赛的核心挑战“协作之谜”中，参赛者们需要处理一个整数序列，将其转化为无向图，并在其中找到一个匹配方案，使得选中边的总“协作价值”最大。

参赛者lukzia被赋予一个整数序列，任务是构造一张无向图，其中每两个满足特定条件的节点之间都有一条边，并且这条边的权重为这两个节点对应值的和。lukzia的目标是找到一组边，使得这些边的权重和最大，且任意两条边没有公共的节点。

描述

给定一个整数序列 a，对于序列中的任意两个位置 i 和 j，如果满足条件 i - j = a[i] - a[j]，则在图中存在一条无向边连接节点 i 和 j，且该边的权重为 a[i] + a[j]。 参赛者需要找到一个匹配，使得匹配中的边权之和最大。如果所有边权都为负数，那么最佳方案是不选择任何边，输出结果为 0。

格式

输入

输入包含多组测试数据。第一行输入一个整数 T，表示测试数据的组数。 对于每组测试数据： 第一行输入一个整数 n（$2 ≤ n ≤ 10^5$），表示序列的长度。 第二行输入 n 个整数 a1, a2, ..., an（$-10^9 ≤ ai ≤ 10^9$），表示序列。 保证所有数据中 n 之和不超过 $9223372036854775807$。

输出

对于每组测试数据，输出一个整数，表示匹配的最大边权之和。

示例

3
9
3 -5 5 6 7 -1 9 1 2
3
-5 -4 -3
3
1 10 100

30
0
0

解释

样例 1：选择连接节点 3 和 5，节点 4 和 7，以及节点 8 和 9 的三条边，得到的最大边权之和为 (5 + 7) + (6 + 9) + (1 + 2) = 30。 样例 2：所有边权都是负数，因此最优匹配是不选择任何边，答案为 0。 样例 3：图中不存在满足条件的边，答案为 0。

提示

无向图的匹配是指在图中选择若干条边，使得任意两条边都没有公共节点。