该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

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

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

输入格式

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

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

下面每组测试数据第一行一个正整数 $n \space (1 \le n \le 10^6)$，表示课程的项目数。

接下来一行 $n$ 个实数 $a_i \space (0 \le a_i \lt 10)$，每个数小数点后都恰有一个数字，表示 $n$ 个项目的得分。

保证所有测试数据中 $n$ 的和不超过 $10^6$。

输出格式

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

样例

样例输入

2
2
4.4 5.4
6
0.4 0.3 7.3 2.3 4.3 3.3

样例输出

10
19