题目描述

Greta 和 Alice 是热门喜剧节目 “QuestExpert” 的两位常驻主持人。本季节目邀请了 $n$ 名程序员完成 Alice 设置的任务。之后，所有人来到演播室，回顾他们完成任务的情况，并进行最后一项演播室任务。

Alice 设计的任务如下。

首先，所有 $n$ 名参与者按编号 $1$ 到 $n$ 逆时针站成一个圆圈。随后 Alice 进行若干轮游戏。

在每一轮中：

1. 每位参与者在一张纸上写下一个整数；
2. Alice 检查这些整数；
3. 对于每个 $i$，若第 $i$ 位参与者写下的数字严格大于逆时针方向的下一位参与者，也就是编号为 $(i\bmod n)+1$ 的参与者所写的数字，则这两位参与者各获得 $1$ 分。

所有轮次结束后，Alice 计算每位参与者的总得分，并告诉 Greta：第 $i$ 位参与者得到了 $a_i$ 分。

Greta 认为数学游戏很无聊，而且这次游戏花费了太长时间。为了证明 Greta 是错的，Alice 决定稍微作弊：她不告诉 Greta 真实的轮数，而是告诉她能够产生这些最终得分的最少轮数。

请帮助 Alice 计算这个最少轮数。

输入格式

每个输入包含多组测试数据。

第一行包含一个整数 $t$，表示测试数据组数。

对于每组测试数据：

• 第一行包含一个整数 $n$，表示参与者人数；
• 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示每位参与者的最终得分。

保证给出的得分确实可以通过至少一轮游戏得到。

输出格式

对于每组测试数据，输出一个整数，表示能够产生给定得分的最少轮数。

样例

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

3
2
2
4
10

数据范围

所有测试数据中的 $n$ 之和不超过 $5\cdot 10^5$。