Xiao De is a teaching assistant at Peking University. Now that the semester has ended, the professor wants Xiao De to calculate the final grades for the students and submit them to the academic office. Based on Xiao De's observations, the process of calculating the final grade can be described as follows:

1. Suppose there are $n$ items in the course, and the score for each item is a real number rounded to one decimal place. Xiao De denotes the multiset of item scores as $S$.

2. The professor repeats an operation several times. In each operation, the professor chooses one of the following two options (A or B) until only one score remains in $S$:

   • A. The professor takes a score $x$ from $S$, rounds $x$ to the nearest integer, and puts it back into $S$ as a new score.
   • B. The professor takes two different scores $x$ and $y$ from $S$, and puts $x+y$ back into $S$ as a new score.

3. The professor takes the only remaining score $x$ in $S$, rounds it to the nearest integer, and submits it to the academic office.

Xiao De is a kind student, and as someone who has been through this, he wants to give the students the highest possible grade. Xiao De wants to know what the maximum grade he can submit to the academic office is, following the rules above. Can you help him?

Input

The input contains multiple test cases.

The first line contains a positive integer $T$, representing the number of test cases.

For each test case, the first line contains a positive integer $n$, representing the number of items in the course.

The next line contains $n$ real numbers $a_i$, each having exactly one digit after the decimal point.

Output

For each test case, output a single integer representing the answer on a new line.

Examples

Input 1

2
2
4.4 5.4
6
0.4 0.3 7.3 2.3 4.3 3.3

Output 1

10
19

Subtasks

For all data: $1 \leq T \leq 10^4, 1 \leq \sum n \leq 10^6$, $0 \leq a_i < 10$.