Description

有 $n$ 座城市，依次坐落在一条直线上，相邻城市之间的距离为$1$，且相邻城市之间原本有一条公路。现在，一场百年难遇的地震导致所有公路都被破坏了。

然而，每座城市都有一台空间传送机，可以从第 $i$ 座城市传送到距离为 $a_i$ 的另一座城市，或者从距离为 $a_i$ 的城市传送到第$i$ 座城市（即从城市 $i$ 可以传送到城市 $i + a_i$ 或$i - a_i$，或者反向传送，如果目标城市存在的话）。

现在，政府需要开展援助工作，希望能尽快实现从任意城市到任意城市的连通性。为此，政府决定修复部分公路。问至少修复多少长度的公路，才能满足上述要求？

Format

Input

第一行一个整数 $T$ ($1 \le T \le 1000$)，表示测试数据组数。

每组输入数据的第一行包含一个正整数 $n$ ($1 \le n \le 3 \times 10^5$)，表示城市数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$)，表示每个城市的传送距离。

保证所有测试数据的 $n$ 之和不超过 $10^6$。

由于输入量可能较大，请使用更快的输入方式。

Output

对于每组数据，输出一行一个整数表示需要最小需要修复公路的长度。

Samples

2
4
1 2 1 3 
5
5 5 5 5 5

0
4