311090: CF1932E. Final Countdown

E. Final Countdowntime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

You are in a nuclear laboratory that is about to explode and destroy the Earth. You must save the Earth before the final countdown reaches zero.

The countdown consists of $n$ ($1 \le n \le 4 \cdot 10^5$) mechanical indicators, each showing one decimal digit. You noticed that when the countdown changes its state from $x$ to $x-1$, it doesn't happen in one move. Instead, each change of a single digit takes one second.

So, for example, if the countdown shows 42, then it will change to 41 in one second, because only one digit is changed, but if the countdown shows 2300, then it will change to 2299 in three seconds, because the three last digits are changed.

Find out how much time is left before the countdown reaches zero.

Input

The first line of input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then the descriptions of the test cases follow.

The first line of each test case contains a single integer $n$ ($1\le n\le 4\cdot 10^5$).

The second line contains a string of $n$ digits, the current state of the countdown. It is guaranteed that at least one digit is not zero.

The sum of $n$ for all tests does not exceed $4\cdot 10^5$.

Output

For each test case, print a single integer without leading zeroes, the number of seconds left before the countdown reaches zero. Note that this number may be huge.

ExampleInput

5
2
42
5
12345
2
99
4
0005
27
456480697259671309012631002

Output

46
13715
108
5
507200774732968121125145546

Note

In the first example, there are four changes that take 2 seconds: 40 to 39, 30 to 29, 20 to 19, and 10 to 09, other changes take 1 second each. So the total time is $2\cdot 4 + 1\cdot(42-4) = 46$.

题目大意：你在一个即将爆炸并摧毁地球的核实验室里。你必须在大倒计时归零之前拯救地球。

倒计时由n（1≤n≤4×10^5）个机械指示器组成，每个指示器显示一个十进制数字。你注意到，当倒计时从x变为x-1时，并不是一次性完成的。相反，每个数字的改变需要一秒钟。

例如，如果倒计时显示42，那么它将在一秒钟内变为41，因为只有一个数字改变了，但如果倒计时显示2300，那么它将在三秒钟内变为2299，因为最后三个数字改变了。

找出倒计时归零之前还剩多少时间。

输入数据格式：第一行输入包含一个整数t（1≤t≤10^4）——测试用例的数量。然后是测试用例的描述。

每个测试用例的第一行包含一个整数n（1≤n≤4×10^5）。

第二行包含一个由n个数字组成的字符串，表示倒计时的当前状态。保证至少有一个数字不是零。

所有测试的n之和不超过4×10^5。

输出数据格式：对于每个测试用例，打印一个整数（不带前导零），表示倒计时归零之前剩余的秒数。注意这个数字可能很大。题目大意：你在一个即将爆炸并摧毁地球的核实验室里。你必须在大倒计时归零之前拯救地球。 倒计时由n（1≤n≤4×10^5）个机械指示器组成，每个指示器显示一个十进制数字。你注意到，当倒计时从x变为x-1时，并不是一次性完成的。相反，每个数字的改变需要一秒钟。 例如，如果倒计时显示42，那么它将在一秒钟内变为41，因为只有一个数字改变了，但如果倒计时显示2300，那么它将在三秒钟内变为2299，因为最后三个数字改变了。 找出倒计时归零之前还剩多少时间。 输入数据格式：第一行输入包含一个整数t（1≤t≤10^4）——测试用例的数量。然后是测试用例的描述。 每个测试用例的第一行包含一个整数n（1≤n≤4×10^5）。 第二行包含一个由n个数字组成的字符串，表示倒计时的当前状态。保证至少有一个数字不是零。 所有测试的n之和不超过4×10^5。 输出数据格式：对于每个测试用例，打印一个整数（不带前导零），表示倒计时归零之前剩余的秒数。注意这个数字可能很大。