Nasser's Product Triples - Repovive Starter Round 5 | Repovive

17B. Nasser's Product Triples

1000 pts1s256 MB

Nasser gives you an array $a$ of length $n$ containing integers from $0$ to $9$ .

Your task is to count the number of ordered triples $(i, j, k)$ such that $1 \le i, j, k \le n$ and the product $a_i \times a_j \times a_k$ is divisible by $5$ .

Note that the indices $i$ , $j$ , and $k$ are not required to be distinct. For example, $(1, 1, 1)$ is a valid triple, meaning you can use the same index more than once.

Input

The first line contains a single integer $t$ ( $1 \le t \le 10^4$ ) - the number of test cases.

For each test case:

The first line contains an integer $n$ ( $1 \le n \le 2 \times 10^5$ ) - the length of the array.
The second line contains $n$ space-separated integers $a_1, a_2, \ldots, a_n$ ( $0 \le a_i \le 9$ ) - the elements of the array.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \times 10^5$ .

Output

For each test case, output a single integer - the number of ordered triples $(i, j, k)$ such that $a_i \times a_j \times a_k$ is divisible by $5$ .

Samples

Input

Case 1

3
1 2 3

Case 2

4
5 0 3 5

Case 3

2
0 5

Case 4

4
9 5 0 1

Case 5

5
5 5 5 5 5

Explanation

$n=2$ , $a=[0, 5]$ :

All $8$ triples $(i, j, k)$ :

Triple $(i, j, k)$	Calculation	Divisible by $5$ ?
$(1,1,1)$	$0 \times 0 \times 0 = 0$	Yes
$(1,1,2)$	$0 \times 0 \times 5 = 0$	Yes
$(1,2,1)$	$0 \times 5 \times 0 = 0$	Yes
$(1,2,2)$	$0 \times 5 \times 5 = 0$	Yes
$(2,1,1)$	$5 \times 0 \times 0 = 0$	Yes
$(2,1,2)$	$5 \times 0 \times 5 = 0$	Yes
$(2,2,1)$	$5 \times 5 \times 0 = 0$	Yes
$(2,2,2)$	$5 \times 5 \times 5 = 125$	Yes

Output

Case 1

Case 2

Case 3

Case 4

Case 5

Nasser gives you an array $a$ of length $n$ containing integers from $0$ to $9$ .

Your task is to count the number of ordered triples $(i, j, k)$ such that $1 \le i, j, k \le n$ and the product $a_i \times a_j \times a_k$ is divisible by $5$ .

Note that the indices $i$ , $j$ , and $k$ are not required to be distinct. For example, $(1, 1, 1)$ is a valid triple, meaning you can use the same index more than once.

The first line contains a single integer $t$ ( $1 \le t \le 10^4$ ) - the number of test cases.

For each test case:

The first line contains an integer $n$ ( $1 \le n \le 2 \times 10^5$ ) - the length of the array.
The second line contains $n$ space-separated integers $a_1, a_2, \ldots, a_n$ ( $0 \le a_i \le 9$ ) - the elements of the array.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \times 10^5$ .

For each test case, output a single integer - the number of ordered triples $(i, j, k)$ such that $a_i \times a_j \times a_k$ is divisible by $5$ .

$n=2$ , $a=[0, 5]$ :

All $8$ triples $(i, j, k)$ :

Triple $(i, j, k)$	Calculation	Divisible by $5$ ?
$(1,1,1)$	$0 \times 0 \times 0 = 0$	Yes
$(1,1,2)$	$0 \times 0 \times 5 = 0$	Yes
$(1,2,1)$	$0 \times 5 \times 0 = 0$	Yes
$(1,2,2)$	$0 \times 5 \times 5 = 0$	Yes
$(2,1,1)$	$5 \times 0 \times 0 = 0$	Yes
$(2,1,2)$	$5 \times 0 \times 5 = 0$	Yes
$(2,2,1)$	$5 \times 5 \times 0 = 0$	Yes
$(2,2,2)$	$5 \times 5 \times 5 = 125$	Yes

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

17B. Nasser's Product Triples

Input

Output

Samples

17B. Nasser's Product Triples

Input

Output

Samples