I. ?!强强!?
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Kendieer 根本就不强！所以他要变得强起来，他想到了一个办法。

他有一个长度为 $$$n$$$ 序列 $$$a$$$，我们定义一个序列的能量为 $$$\sum_{i=1}^n a_i$$$，即这个序列所有元素的总和。

你可以对任意一个无前导零的数字执行任意次（包括 $$$0$$$ 次）以下操作，其代价为累加：

  • 将该数字任意一个数位从 $$$x$$$ 修改到 $$$y$$$，其需要代价为 $$$|x-y|$$$，允许操作后的数字含有前导零。

例如：

  • 从 $$$123$$$ 修改成 $$$223$$$ 代价为 $$$1$$$。
  • 从 $$$235$$$ 修改成 $$$295$$$ 代价为 $$$6$$$。
  • 从 $$$235$$$ 修改成 $$$325$$$ 代价为 $$$2$$$。

此外，我们定义最终能量为修改后的序列能量减去修改操作所需的代价。

现在，Kendieer 想最大化最终能量，从而显得他很强（其实并非强），请你输出这个序列可能的最大最终能量。

Input

第一行输入一个正整数 $$$T(1\le T\le 10^4)$$$，表示测试数据组数。

接下来的 $$$T$$$ 组数据中，每组数据输入如下：

  • 第一行输入一个正整数 $$$n(1\le n\le 2\times 10^5)$$$，表示序列长度。
  • 第二行输入一个 $$$n$$$ 个正整数 $$$a_1,a_2,\dots ,a_n(1\le a_i\le 10^9)$$$，表示序列。保证所有数字均无前导零。

此外，数据保证所有测试点 $$$n$$$ 的总和不超过 $$$2\times 10^5$$$。

Output

对于每组测试，共输出一个整数，表示答案。

Example
Input
3
6
1 1 4 5 1 4
9
9 9 8 2 4 4 3 5 3
3
233 1919810 998244353
Output
16
47
1010000910
Note

对于第一组测试，不修改即可达到最大化最终能量。

对于第二组测试，一种可行的方案是将序列修改成 $$$[9,9,8,8,7,7,6,6,5]$$$，其代价为 $$$18$$$，可以证明不存在最终能量更优的操作方案。