← 返回题目列表

Codeforces · 1932/E

E. 最后倒计时

中文机器翻译题面 查看原题

你身处一个即将爆炸并摧毁地球的核实验室。您必须在最终倒计时归零之前拯救地球。

倒计时由 $$$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$$$。