数组 $$$a_1, a_2, \ldots, a_n$$$ 是好的,当且仅当对于每个子段 $$$1 \leq l \leq r \leq n$$$,以下成立: $$$a_l + a_{l + 1} + \ldots + a_r = \frac{1}{2}(a_l + a_r) \cdot (r - l + 1)$$$。
给定一个整数数组 $$$a_1, a_2, \ldots, a_n$$$。在一次操作中,您可以将此数组的任何一个元素替换为任何实数。求出使该数组正常运行所需的最少操作数。
输入
第一行输入包含一个整数 $$$t$$$ ($$$1 \leq t \leq 100$$$):测试用例的数量。
接下来的 $$$t$$$ 行包含测试用例的描述。
在第一行中,您将获得一个整数 $$$n$$$ ($$$1 \leq n \leq 70$$$):数组中整数的数量。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-100 \leq a_i \leq 100$$$):初始数组。
输出
对于每个测试用例,打印一个整数:为使给定数组正常运行而需要替换的最小元素数。
示例
输入 #1
5 4 1 2 3 4 4 1 1 2 2 2 0 -1 6 3 -2 4 -1 -4 0 1 -100
输出 #1
0 2 0 3 0
注意
在第一个测试用例中,数组已经很好了。
在第二个测试用例中,可能的好数组之一是 $$$[1, 1, \underline{1}, \underline{1}]$$$ (替换的元素带有下划线)。
在第三个测试用例中,数组已经很好了。
在第四个测试用例中,可能的好数组之一是 $$$[\underline{-2.5}, -2, \underline{-1.5}, -1, \underline{-0.5}, 0]$$$。