Description

简要题面

这里我们定义一个电脑运行 $a+b$ 的速度是 $a+b$ 中出现的进位的次数。

给定一个数组 $a_1,a_2,...,a_n$，请找出正确的排序使得计算这个数组的和时运行的速度最短，请找出最少的进位次数。

Input Format

本题有多组数据。

第一行一个整数 $T$，表示数据组数。

对于每组数据：

第一行一个整数 $n$。

接下来一行 $n$ 个整数，表示输入的数组 $a$。

Output Format

对于每组数据，输出最小的进位次数。

2
3
9 99 999
1
12345

5
0

Hint

对于 $100 \%$ 的数据： $1 \leq \sum n \leq 10^5$， $1 \leq a_i \leq 10^9$