Geumjae 有一个由 $$$n$$$ 零组成的数组 $$$a$$$。他的目标是使用最少的操作次数将其转换为给定的目标数组。
他可以任意次数、任意顺序执行以下两种类型的操作:
- 增加:选择任意正整数$$$x$$$。增加 全部 数组 $$$a$$$ 的元素由 $$$x$$$ 组成。换句话说,他选择一个正整数 $$$x$$$,并且对于每个 $$$i$$$ ($$$1 \le i \le n$$$),他将 $$$a_i$$$ 替换为 $$$a_i + x$$$。
- 粉碎:设置 一些 数组 $$$a$$$ 到 $$$0$$$ 的 元素(可能没有或全部)。换句话说,对于每个$$$i$$$ ($$$1 \le i \le n$$$),他要么用$$$0$$$替换$$$a_i$$$,要么像以前一样保留它。
给定数组 $$$a$$$ 的最终目标状态,找到最小操作总数(两者 增加 和 粉碎) Geumjae 需要表演。
可以证明,对于任何给定的最终数组,操作序列始终存在。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$) — 数组 $$$a$$$ 中的元素数量。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 100$$$) — 目标数组 $$$a$$$ 的元素。
输出
对于每个测试用例,输出一个整数 - 所需的最少操作数。
示例
输入复制
331 1 3110099 9 3 2 4 4 8 5 3
输出复制
3111
注意
第一个测试用例的说明:
目标数组是$$$[1, 1, 3]$$$。 3 个操作的可能序列(这是最少的)是:
- 最初,数组为 $$$[0, 0, 0]$$$。经过一个 增加 与 $$$x = 2$$$ 进行运算,数组变为 $$$[2, 2, 2]$$$。
- 接下来,经过 粉碎 对前两个元素进行操作,数组变为$$$[0, 0, 2]$$$。
- 最后,经过 增加 与 $$$x = 1$$$ 的运算,数组变为 $$$[1, 1, 3]$$$。
我们使用了$$$2$$$ 增加 操作和 $$$1$$$ 粉碎 操作总共 $$$3$$$ 操作。
第二个测试用例说明:
目标数组是$$$[100]$$$。单个 增加 与 $$$x = 100$$$ 的运算给出目标数组。