Codeforces Round 927 (Div. 3) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

implementation

math

number theory

*1600

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Final Countdown

time limit per test

2 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputYou 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.

Example

Input

52425123452994000527456480697259671309012631002

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$$$.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Nov/09/2024 10:14:00 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|