题目描述

你在一个核实验室里，实验室即将爆炸，地球将会毁灭。你必须在倒计时归零之前拯救地球。

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