Mabư Béo, gặp lại hai bậc sư phụ: Goku và Piccolo. Họ cùng với những võ sĩ quyền năng khác ngồi cùng nhau thành một vòng tròn. Mabư Béo phát cho mọi người trong vòng tròn chút bánh quy, và hắn ta đặt ra cho mọi người bài toán:

Vòng tròn có ~N~ võ sĩ, đánh số từ ~0~ đến ~N - 1~. Võ sĩ thứ ~i~ sở hữu ~A_i~ miếng bánh quy. Với mọi ~i~ từ ~1~ đến ~N - 1~, võ sĩ thứ ~i~ sẽ ngồi bên tay phải võ sĩ thứ ~i - 1~. Võ sĩ được đánh số ~0~ sẽ ngồi bên tay phải võ sĩ được đánh số ~N - 1~. Mabư Béo ngồi ở vị trí được đánh số ~0~ trong vòng tròn.

Mỗi lượt chơi, ngoại trừ lượt đầu tiên, võ sĩ vừa nhận được bánh quy của lượt trước đó sẽ đưa đúng ~\lceil \frac{j + 1}{2} \rceil~ miếng bánh quy cho võ sĩ ngồi bên phải mình. Trong đó, ~j~ thể hiện số lượt chơi đã diễn ra trước lượt chơi hiện tại. Trong trường hợp lượt chơi đầu tiên, Mabư Béo sẽ là người thực hiện. Hắn ta sẽ đưa ~\lceil \frac{0 + 1}{2} \rceil = 1~ miếng bánh quy cho võ sĩ ngồi bên phải mình.

Trò chơi kết thúc khi một võ sĩ không thể thực hiện lượt chơi khi đến lượt mình (không đủ bánh quy để thực hiện lượt chơi). Nói cách khác, trò chơi kết thúc ở lượt chơi mà số bánh mà lượt chơi đó yêu cầu lớn hơn số bánh người chơi lượt đó sở hữu. Khi đó, người chơi không thể thực hiện lượt chơi của mình sẽ bị coi là thua cuộc.

Hãy in ra chỉ số của võ sĩ sẽ thua cuộc trong trò chơi này.

Với một số thực ~x~ bất kỳ, ~\lceil x \rceil~ là số nguyên nhỏ nhất thỏa mãn lớn hơn hoặc bằng ~x~. Ví dụ: ~\lceil 5.3 \rceil = 6~, ~\lceil \sqrt{3} \rceil = 2~, ~\lceil 4.0 \rceil = 4~.

Input

Mỗi file test sẽ chứa nhiều trường hợp test. Dòng đầu tiên chứa số trường hợp test ~T~ (~1 \le T \le 1000~). Mô tả một trường hợp test như sau:

Dòng đầu chứa số nguyên ~N~ (~3 \le N \le 10^5~) - số võ sĩ trong vòng tròn.

Dòng thứ hai chứa ~N~ số nguyên ~A_0, A_1, \ldots, A_{N - 1}~ (~1 \le A_i \le 10^9~) - số bánh quy mỗi võ sĩ có khi bắt đầu trò chơi.

Dữ liệu đảm bảo rằng tổng của ~N~ qua tất cả trường hợp test sẽ không vượt quá ~10^5~.

Output

Với mỗi trường hợp test, in ra một số nguyên duy nhất trên một dòng, thể hiện chỉ số của võ sĩ sẽ thua cuộc trong trò chơi này.

Sample Input 1

5
3
3 2 2
4
3 1 4 2
7
5 4 3 2 3 2 2
10
10 9 8 7 6 5 4 3 2 1
11
11 10 9 8 7 6 5 4 3 2 1

Sample Output 1

2
0
6
8
10

Notes

Mô tả những lượt chơi đầu ở trường hợp test đầu tiên:

Số bánh các võ sĩ sở hữu ban đầu: ~3~, ~2~, ~2~.

Lượt đầu, Mabư Béo (có chỉ số ~0~) sẽ đưa ~\lceil \frac{0 + 1}{2} \rceil = 1~ bánh quy cho võ sĩ ngồi bên phải mình.

Số bánh các võ sĩ sở hữu hiện tại: ~2~, ~3~, ~2~.

Lượt thứ hai, võ sĩ có chỉ số ~1~ sẽ đưa ~\lceil \frac{1 + 1}{2} \rceil = 1~ bánh quy cho võ sĩ ngồi bên phải mình.

Số bánh các võ sĩ sở hữu hiện tại: ~2~, ~2~, ~3~.

Lượt thứ ba, võ sĩ có chỉ số ~2~ sẽ đưa ~\lceil \frac{2 + 1}{2} \rceil = 2~ bánh quy cho võ sĩ ngồi bên phải mình.

Số bánh các võ sĩ sở hữu hiện tại: ~4~, ~2~, ~1~.

Lượt thứ tư, võ sĩ có chỉ số ~0~ sẽ đưa ~\lceil \frac{3 + 1}{2} \rceil = 2~ bánh quy cho võ sĩ ngồi bên phải mình.

Số bánh các võ sĩ sở hữu hiện tại: ~2~, ~4~, ~1~.

Lượt thứ năm, võ sĩ có chỉ số ~1~ sẽ đưa ~\lceil \frac{4 + 1}{2} \rceil = 3~ bánh quy cho võ sĩ ngồi bên phải mình.

Số bánh các võ sĩ sở hữu hiện tại: ~2~, ~1~, ~4~.