你身处一个即将爆炸并摧毁地球的核实验室。您必须在最终倒计时归零之前拯救地球。
倒计时由 $$$n$$$ ($$$1 \le n \le 4 \cdot 10^5$$$) 机械指示器组成,每个指示器显示一位十进制数字。您注意到,当倒计时的状态从 $$$x$$$ 更改为 $$$x-1$$$ 时,它不会一次性发生。相反,每更改一个数字都需要一秒钟。
因此,例如,如果倒计时显示 42,那么它将在一秒内更改为 41,因为只更改了一位数字,但如果倒计时显示 2300,那么它将在三秒内更改为 2299,因为最后三位数字更改了。
找出倒计时归零之前还剩多少时间。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。然后是测试用例的描述。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\le n\le 4\cdot 10^5$$$)。
第二行包含一串 $$$n$$$ 数字,表示倒计时的当前状态。保证至少一位数字不为零。
所有测试的 $$$n$$$ 总和不超过 $$$4\cdot 10^5$$$。
输出
对于每个测试用例,打印一个不带前导零的整数,即倒计时达到零之前剩余的秒数。请注意,这个数字可能很大。
示例
输入 #1
5 2 42 5 12345 2 99 4 0005 27 456480697259671309012631002
输出 #1
46 13715 108 5 507200774732968121125145546
注意
在第一个示例中,有四个更改需要 2 秒:40 到 39、30 到 29、20 到 19 和 10 到 09,其他更改每个需要 1 秒。所以总时间是$$$2\cdot 4 + 1\cdot(42-4) = 46$$$。