小德是北京大学的一名学生助教。现在一学期的课程结束了，老师希望小德能统计学生的最终成绩，并提交给教务。根据小德的观察，一位老师累加分数的过程可以被下述过程描述：

1. 假设这一门课程有 $n$ 个项目，每个项目的得分都是一个保留到小数点后一位的实数。小德记项目得分的可重集合为 $S$。
2. 重复若干次操作，每一次操作老师会从下面 A,B 两个方案中选择一个执行，直到 $S$ 只剩下一个项目得分：
   • A. 老师在 $S$ 中取出一个项目的得分 $x$，将 $x$ 四舍五入到整数后作为新的项目得分放回 $S$。
   • B. 老师在 $S$ 中取出两个不同的项目的得分 $x,y$，将 $x+y$ 作为新的项目得分放回 $S$。
3. 老师取出 $S$ 中唯一的项目得分 $x$，将 $x$ 四舍五入到整数后提交给教务。

小德是一名善良的学生，作为过来人，他希望给学生尽可能高的成绩。小德想知道，按照上述加分规则，他提交给教务的成绩最高可能是多少，你能帮帮他吗？

输入格式

本题的测试点包含有多组测试数据。

第一行一个正整数 $T$ 表示测试数据组数。

下面每组测试数据第一行一个正整数 $n$，表示课程的项目数。

接下来一行 $n$ 个实数 $a_i$，每个数小数点后都恰有一个数字。

输出格式

对于每组数据，一行一个整数表示答案。

样例数据

输入格式

2
2
4.4 5.4
6
0.4 0.3 7.3 2.3 4.3 3.3

输出格式

10
19

子任务

对于所有数据：$1 \leq T \leq 10^4, 1 \leq \sum n \leq 10^6$, $0 \leq a_i \lt 10$。