Greta 和 Alice 是热门喜剧节目“QuestExpert”的两名常驻主持人。本季节目中，她们邀请了 $n$ 名程序员来完成由 Alice 设计的任务。之后，他们齐聚演播室，回顾大家的表现并完成最后的演播室任务。

今天，Alice 想出的演播室任务如下：首先，所有 $n$ 名参与者按逆时针方向从 $1$ 到 $n$ 围成一个圈。然后 Alice 进行若干轮游戏。在每一轮中，每个参与者都在一张纸上写下一个整数。之后，Alice 检查这些数字，对于每个从 $1$ 到 $n$ 的 $i$，如果第 $i$ 个参与者的数字严格大于逆时针方向下一个参与者（即编号为 $(i \bmod n) + 1$ 的参与者）的数字，则第 $i$ 个和第 $(i \bmod n) + 1$ 个参与者都获得一分。所有轮次结束后，Alice 计算每个参与者的总得分并报告给 Greta。结果显示，第 $i$ 个参与者得到了 $a_i$ 分。

Greta 认为数学游戏很无聊，而且这个游戏耗时太长。为了证明她是错的，Alice 决定稍微作弊一下：她不告诉 Greta 实际的游戏轮数，而是告诉她能够使得每个 $i$ 的第 $i$ 个参与者仍然获得 $a_i$ 分的最小可能轮数。

请帮助 Alice 确定这个轮数。

输入格式

每个测试点包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^4$)。接下来是测试用例的描述。

每个测试用例的第一行包含一个整数 $n$，表示参与者的数量 ($2 \le n \le 5 \cdot 10^5$)。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示参与者的最终得分 ($0 \le a_i \le 10^9$)。保证这些得分是在上述游戏中通过至少一轮游戏得到的。

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

输出格式

对于每个测试用例，在单独的一行中输出可能导致给定得分的最小轮数。

样例

输入 1

5
2
3 3
3
2 2 2
4
1 2 4 3
5
0 2 3 5 4
6
5 8 3 10 14 4

输出 1

3
2
2
4
10