Devin 是一位科技公司的系统管理员，负责管理一个环形拓扑结构的网络，其中有 $n$ 台服务器。每台服务器处理一定量的计算负载，用非负整数 $a_i$ 表示，其中 $i$ 的范围从 $1$ 到 $n$。

为了优化网络性能并确保公平性，Devin 希望均衡所有服务器的负载，使每台服务器处理相同数量的负载。他的目标是尽可能最大化这个相等的负载值。

Devin 开发了一个脚本来减少服务器上的负载。当他在服务器 $i$ 上运行该脚本时，它本应将该服务器的负载减少 $2$ 个单位（最低减至零）。然而，由于脚本中存在一个已知的错误，每次在服务器 $i$ 上执行时，它还会无意中从网络中的前一台服务器（服务器 $i-1$）中额外移除 $1$ 个单位的负载。如果 $i=1$，则前一台服务器是服务器 $n$（因为服务器构成一个环）。

Devin 可以运行这个有问题的脚本任意次数（包括零次），每次可以选择任意一台服务器来运行。即使服务器当前的负载小于 $2$ 个单位，或者前一台服务器的负载为零，他也可以在服务器上运行该脚本（在这两种情况下，负载都会变为零）。

请帮助 Devin 确定使用他的脚本后，所有服务器上能够达到的最大相等负载。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^4$)。

接下来是各测试用例的描述。 每个测试用例的第一行包含一个整数 $n$，表示服务器的数量 ($2 \le n \le 2 \cdot 10^5$)。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示服务器当前处理的负载量 ($0 \le a_i \le 10^9$)。

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

输出格式

对于每个测试用例，输出所有服务器能够达到的最大相等负载。

样例

输入 1

5
4
9 9 6 8
2
3 5
9
9 9 8 2 4 4 3 5 3
3
777 777 777
6
0 1 0 1 0 1

输出 1

5
1
0
777
0

说明

在第一个测试用例中，Devin 可以在服务器 $1$ 上运行一次脚本，在服务器 $2$ 上运行两次，在服务器 $4$ 上运行一次。结果，每台服务器将处理 $5$ 个单位的负载。