给你一个带有 $$$n$$$ 数字的数字时钟。每个数字显示从 $$$0$$$ 到 $$$9$$$ 的整数,因此整个时钟显示从 $$$0$$$ 到 $$$10^n-1$$$ 的整数。如果数字小于 $$$10^{n-1}$$$,时钟将显示前导零。
您希望时钟通过尽可能少的操作来显示 $$$0$$$。在操作中,您可以执行以下操作之一:
- 将时钟上的数字减少$$$1$$$,或者
- 交换两个数字(您可以选择要交换的数字,并且它们不必相邻)。
您的任务是确定使时钟显示 $$$0$$$ 所需的最少操作次数。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^3$$$)。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$) — 时钟上的位数。
每个测试用例的第二行包含一串 $$$n$$$ 数字 $$$s_1, s_2, \ldots, s_n$$$ ($$$0 \le s_1, s_2, \ldots, s_n \le 9$$$) — 时钟上的数字。
注意:如果数字小于 $$$10^{n-1}$$$,时钟将显示前导零。
输出
对于每个测试用例,打印一个整数:使时钟显示 $$$0$$$ 所需的最少操作数。
示例
输入 #1
7 3 007 4 1000 5 00000 3 103 4 2020 9 123456789 30 001678294039710047203946100020
输出 #1
7 2 0 5 6 53 115
注意
在第一个示例中,最好只减少 $$$7$$$ 次。
在第二个例子中,我们可以先交换第一个和最后一个位置,然后将数字减少$$$1$$$。
在第三个例子中,时钟已经显示$$$0$$$,所以我们不必执行任何操作。