小苯的数位排序

题号：NC315804
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 小苯得到了一个长度为 $n$ 的正整数数组 $a_1, a_2, \dots, a_n$ 。
$\hspace{15pt}$ 他可以进行若干次操作。每次操作中，他需要选择一个下标 $i\ (1 \leqq i \leqq n)$ ，然后将 $a_i$ 替换为它的各位数字之和。
$\hspace{15pt}$ 形式化地，若当前 $a_i = x$ ，那么操作后：
$a_i \leftarrow \operatorname{digit\_sum}(x)$
$\hspace{15pt}$ 其中 $\operatorname{digit\_sum}(x)$ 表示十进制下 $x$ 的各位数字之和。

$\hspace{15pt}$ 例如：
$\hspace{23pt}\bullet$ $\operatorname{digit\_sum}(38) = 3 + 8 = 11$ 。
$\hspace{23pt}\bullet$ $\operatorname{digit\_sum}(11) = 1 + 1 = 2$ 。
$\hspace{15pt}$ 小苯希望经过若干次操作后，使整个数组变成非递减数组。

$\hspace{15pt}$ 你的任务就是求出最少需要多少次操作；如果无论如何都无法做到，输出 $-1$ 。

输入描述:

第一行输入一个整数 ，表示测试数据组数。
第一行输入一个整数 ，表示数组长度。
第二行输入  个正整数 ，表示初始数组。

保证所有测试数据中， 的总和不超过 。

输出描述:

对于每组测试数据，输出一个整数，表示最少需要多少次操作；如果无法变成非递减数组，则输出 。

示例1

输入

复制

4
4
99 10 10 10
3
100 19 10
2
29 1
5
1 2 3 3 9

输出

复制

说明

对于第一组数据，只需要对第一个数操作两次：
 。
 。
最终数组变成 ，答案为 。
对于第二组数据，可以先把  变成 ，再把  变成 ，最终得到 ，答案为 。
对于第三组数据， 最多只能继续变成 ，再变成 ，但最后仍有 ，因此无解。
对于第四组数据，原数组本身已经是非递减的，所以答案为 。