题目描述

小苯有 $n$ 张纸牌，每张纸牌都有一个权值，用数组 $a_1,a_2,\dots,a_n$ 表示，第 $i$ 张牌的权值为 $a_i$。 小苯想要搭建一个纸牌屋，如下图所示： 一个四层的纸牌屋，其中包含 $30$ 张纸牌 具体的，一个 $k$ 层的纸牌屋是按图示方式无限延伸的图形的前 $k$ 层，其中每条边都是一张纸牌。 小苯想要选择若干张连续的纸牌（即数组的一个非空子数组）来搭建一个纸牌屋，他希望不浪费任何一张纸牌，所以他选择的纸牌数量必须恰好能够搭成某个层数为正整数的纸牌屋。 请你帮小苯找出，所有选择方案中所有纸牌的权值之和最大的那一个。你只需要输出目标方案的权值之和即可。 【名词解释】 子数组：从原数组中，连续的选择一段元素（可以全选、可以不选）得到的新数组。官方中文

输入格式

每个测试文件均包含多组测试数据。第一行输入一个整数 $T\left(1\leq T\leq 10^4\right)$ 代表数据组数，每组测试数据描述如下：官方中文

第一行输入一个整数 $n\left(3 \leq n \leq 2\times 10^5\right)$。 第二行输入 $n$ 个整数 $a_1, a_2,\dots,a_n\left( -10^9 \leq a_i \leq 10^9\right)$。官方中文

除此之外，保证单个测试文件的 $n$ 之和不超过 $2 \times 10^5$。官方中文

输出格式

对于每组测试数据，新起一行。官方中文

输出一个整数，代表目标方案的权值之和。官方中文

说明

在大部分情况下，PyPy 的运行速度优于 Python。本题我们建议您选择对应版本的 PyPy 进行提交、而不是 Python。官方中文