B-爱的魔法_华中农业大学第十五届程序设计竞赛（新生赛）同步赛

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

给定一个序列 $[a_1, a_2, \ldots, a_n]$ 。对于数组中的每一个元素 $a_i$ ，你可以执行最多一次操作：交换该元素的任意两个数位（不考虑前导 $0$ ）。

例如，对于元素 $12305$ ，你可以通过一次操作使其变为 $12503$ ，或者变为 $2315$ 。但是，你不能将 $123$ 变为 $2103$ 。

请求出执行这些操作后，整个序列元素和的最大值。

输入包含多组数据。

首先输入一行一个整数  ()，表示数据的组数。

对于每组数据，首先输入一行一个整数  ()，表示序列的长度。

接下来输入一行  个整数  ()，表示给定的序列。

保证对于一个测试点的所有数据， 的和不超过 。

对于每组数据，输出一行一个整数，表示执行操作后元素和的最大值。

示例1

复制

3
3
1234 9123 555
6
11 41 51 41 919 810
1
100

复制

14107
1945
100

在第一组数据中，我们可以交换  的千位和个位得到 ，交换  的百位和个位得到 。最终得到的序列为 ，和为 。