F. doubleNmod - Turqoize
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Anton and Azoz were busy playing Valorant while working from home, everyone kept nagging about it so they gave them this question to get distracted.

Given an array of integers $$$a$$$ of size $$$n$$$. You can do the following operation any number of times (possibly zero):

  • Choose any index $$$i$$$ and set $$$a_i$$$ = ($$$2$$$ . $$$a_i$$$) mod $$$10$$$
Your goal is to find the minimum number of operations to make them all equal, or print -1 if it is not possible.
Input

The first line of input contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$).

The first line of the test case contains one integer $$$n$$$ $$$(1 \le n \le 10^5)$$$.

The second line of the test case contains $$$n$$$ integers $$$a_1,a_2,...,a_n$$$ $$$(0 \le a_i \le 10^9)$$$, where $$$a_i$$$ is the $$$i$$$-th element of $$$a$$$.

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

Output

For each test case on a separate line, output a single integer - the minimum number of operations to make them all equal, or -1 if it is not possible.

Example
Input
4
3
17 4 2
4
4 4 8 8
2
1 8
4
21 21 21 21
Output
2
2
3
0
Note

In the first test case we can do the following:

  • Perform an operation on the first index. $$$(17 * 2)$$$ mod $$$10 = 4$$$
  • Perform an operation on the third index. $$$(2 * 2)$$$ mod $$$10 = 4$$$
The minimum number of operations to make all elements equal is 2.