有n堆石头，第i堆有hi个石子，你可以用以下操作来改变石堆里的石子数：
1）你对第3堆到第n堆操作
2）当前堆的编号记为i
3）你可以选择一个数字d（0=<3*d<=hi)，从第i堆移d个石子到第i-1堆，从第i堆移2*d个石子到第i-2堆。
      第i堆减少了3d，第i-1堆增加了d，第i-2堆增加了2d
4）不同次操作可选不同或相同的数d，不含石子的空堆仍然算堆。
请问操作后含石子最少的堆最多有多少石子？

多组数据，第一行的t(1<=t<=200000)表示数据组数。每组数据第一行为n(3=<n<=200000)，第二行包括n个数h1,h2,......hn（1<=hi<=1000000000）。
保证所有测试数据的n的和不超过200000。

对每组输入，输出含石子最少的堆最多有多少石子。

4
4
1 2 10 100
4
100 100 100 1
5
5 1 1 1 8
6
1 2 3 4 5 6

7
1
1
3

第一个样例中，最初的堆为1，2，10，100。将第3堆的3个石子移到第2堆，6个石子移到第1堆，变为7，5，1，100.
将第4堆的6个石子移到第3堆，12个石子移到第2堆，变为7，17，7，82.
第2个样例中，最后一堆为1.
第3个样例中，最好不进行任何操作。
第4个样例中，最后堆变为3，5，3，4，3，3