P9676 [ICPC 2022 Jinan R] Skills

庞博士有 $3$ 项技能：喝汽水、猎狐和炒股，编号分别为 $1,2,3$。初始时，每项技能的熟练度为 $0$。 接下来有 $n$ 天。在第 $i$ 天，庞博士可以选择一项技能（假设是第 $j$ 项）进行练习，然后在这天结束时让这项技能的熟练度增加 $a_{i,j}(0\leq a_{i,j}\leq 10000)$。同时，如果某一项技能（假设是第 $k$ 项）已经有 $x$ 天没有练习，那么在这天结束时，这项技能的熟练度会减少 $x$。当然，任何一项技能的熟练度都不可能小于 $0$。 现在，庞博士想知道：在第 $n$ 天结束后，这 $3$ 项技能的熟练度之和最大为多少。由于他非常忙，而且他的日程和对习惯的适应程度可能有变，所以庞博士把这 $T$ 个问题交给了你——每个问题的内容都一样，只是给出的数据可能有所不同而已。

第一行，一个正整数 $T~(1 \leq T \leq 1000)$，表示数据组数。 对于每组数据，输入 $(n + 1)$ 行。 * 第一行，一个正整数 $n~(1 \leq n \leq 1000)$，表示天数。 数据保证单个测试点内的 $\sum n$ 不超过 $1000$。

对于每组数据，输出 $1$ 行 $1$ 个数，表示答案。