Shohag 有一个整数序列 $$$a_1, a_2, \ldots, a_n$$$。他可以执行以下操作任意次数(可能为零):
- 选择任何正整数$$$k$$$(在不同的操作中可以不同)。
- 选择序列中的任意位置(可能是序列的开头或结尾,或者任意两个元素之间)并将 $$$k$$$ 插入序列中的该位置。
- 这样,序列 $$$a$$$ 发生变化,并且对这个变化的序列执行下一个操作。
例如$$$a=[3,3,4]$$$,选择$$$k = 2$$$,则运算后可以得到序列$$$[\underline{2},3,3,4]$$$、$$$[3,\underline{2},3,4]$$$之一, $$$[3,3,\下划线{2},4]$$$,或$$$[3,3,4,\下划线{2}]$$$。
Shohag 希望这个序列满足以下条件:对于每个 $$$1 \le i \le |a|$$$,$$$a_i \le i$$$。这里,$$$|a|$$$表示$$$a$$$的大小。
帮助他找到实现这一目标所需执行的最少操作数。我们可以证明,在问题的约束下,总是可以通过有限数量的操作来实现这一目标。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 200$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$) — 序列的初始长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 序列的元素。
输出
对于每个测试用例,打印一个整数 - 实现声明中提到的目标所需执行的最少操作数。
示例
输入 #1
4 3 1 3 4 5 1 2 5 7 4 1 1 3 69 6969 696969
输出 #1
1 3 0 696966
注意
在第一个测试用例中,我们必须执行至少一个操作,如 $$$a_2=3>2$$$。我们可以执行 $$$[1, 3, 4] \rightarrow [1, \underline{2}, 3, 4]$$$ 操作(新插入的元素带有下划线),现在条件满足了。
在第二个测试用例中,Shohag 可以执行以下操作:
$$$[1, 2, 5, 7, 4] \rightarrow [1, 2, \underline{3}, 5, 7, 4] \rightarrow [1, 2, 3, \underline{4}, 5, 7, 4] \rightarrow [1, 2, 3, 4, 5, \underline{3}, 7, 4]$$$。
在第三个测试用例中,序列已经满足条件。