#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/8/problems/b

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/8/problems/b

Repovive

Not Divisable by 10 - Repovive Standard Round 3 | Repovive | Repovive

Back

Code

Upload

Submissions

Learn

8B. Not Divisable by 10

1000 ptstype :zen to enter zen mode

by AmirMohammad Shahrezaei (AmShZ)

Time: 1sMemory: 128 MB

You are given an array $a_1, a_2, \ldots, a_n$ .

You may delete any number of elements from the array, possibly zero or all of them. The cost of your choice is the sum of the deleted elements.

Your goal is to make the product of the remaining elements not divisible by $10$ .

If all elements are deleted, the product of the empty array is considered to be $1$ .

Find the minimum possible cost.

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$1 \le a_i \le 1000$
The sum of $n$ over all test cases is at most $2 \times 10^5$

Input

t

\left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array} \right\} \times t

Output

\left. \begin{array}{l} ans \end{array} \right\} \times t

Samples

Input

Case 1

3
2 3 5

Case 2

4
1 3 7 11

Case 3

3
10 20 30

Case 4

5
6 25 4 15 7

Case 5

4
2 8 14 21

Explanation

Case 1

Delete $2$ . The remaining product is $3 \times 5 = 15$ , which is not divisible by $10$ .

Case 2

Delete nothing. The product is $1 \times 3 \times 7 \times 11 = 231$ , which is not divisible by $10$ .

Case 3

Delete $10$ , $20$ , and $30$ . The remaining product is $1$ , which is not divisible by $10$ .

Case 4

Delete $6$ and $4$ . The remaining product is $25 \times 15 \times 7 = 2625$ , which is not divisible by $10$ .

Case 5

Delete nothing. The product is $2 \times 8 \times 14 \times 21 = 4704$ , which is not divisible by $10$ .

Output

Case 1

Case 2

Case 3

Case 4

Case 5

You are given an array $a_1, a_2, \ldots, a_n$ .

You may delete any number of elements from the array, possibly zero or all of them. The cost of your choice is the sum of the deleted elements.

Your goal is to make the product of the remaining elements not divisible by $10$ .

If all elements are deleted, the product of the empty array is considered to be $1$ .

Find the minimum possible cost.

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$1 \le a_i \le 1000$
The sum of $n$ over all test cases is at most $2 \times 10^5$

t

\left. \begin{array}{l} n \\ a_1 \quad a_2 \quad \cdots \quad a_n \end{array} \right\} \times t

\left. \begin{array}{l} ans \end{array} \right\} \times t

Delete $2$ . The remaining product is $3 \times 5 = 15$ , which is not divisible by $10$ .

Delete nothing. The product is $1 \times 3 \times 7 \times 11 = 231$ , which is not divisible by $10$ .

Delete $10$ , $20$ , and $30$ . The remaining product is $1$ , which is not divisible by $10$ .

Delete $6$ and $4$ . The remaining product is $25 \times 15 \times 7 = 2625$ , which is not divisible by $10$ .

Delete nothing. The product is $2 \times 8 \times 14 \times 21 = 4704$ , which is not divisible by $10$ .