E. Финальный отсчёт
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы находитесь в ядерной лаборатории, которая готовится взорваться и уничтожить Землю. Вы должны спасти Землю, прежде чем финальный отсчёт достигнет нуля.

Отсчёт состоит из $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число без ведущих нулей, количество секунд, оставшихся до того, как отсчёт достигнет нуля. Обратите внимание, что это число может быть огромным.

Пример
Входные данные
5
2
42
5
12345
2
99
4
0005
27
456480697259671309012631002
Выходные данные
46
13715
108
5
507200774732968121125145546
Примечание

В первом примере есть четыре изменения, которые занимают 2 секунды: 40 до 39, 30 до 29, 20 до 19 и 10 до 09, другие изменения занимают по 1 секунде каждое. Таким образом, общее время составляет $$$2\cdot 4 + 1\cdot(42-4) = 46$$$.