Split by GCD - Repovive Starter Round 6 | Repovive

19G. Split by GCD

3500 pts2s256 MB

You are given an array $a$ of length $n$ .

You may delete any number of its elements. After the deletions, you must divide all remaining elements into exactly two non-empty groups. Every remaining element must belong to exactly one of the groups.

The greatest common divisor of all elements in each group must be greater than $1$ .

Find the minimum number of elements that must be deleted. If it is impossible to form such two groups, output $-1$ .

The greatest common divisor of a group containing one element is equal to that element.

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$1 \le a_i \le 2 \times 10^5$
The sum of $n$ over all test cases does not exceed $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

5
6 10 15 7 1

Case 2

6
6 10 14 15 21 35

Explanation

Case 1

Delete $7$ and $1$ . The remaining elements can be divided into $\{6,10\}$ , whose gcd is $2$ , and $\{15\}$ , whose gcd is $15$ . No valid division can keep four elements.

Case 2

Delete $21$ . The other five elements can be divided into $\{6,14\}$ , whose gcd is $2$ , and $\{10,15,35\}$ , whose gcd is $5$ . It is impossible to divide all six elements validly.

Output

Case 1

Case 2

Input

Case 1

1
2

Case 2

7
2 3 5 7 11 13 1

Case 3

6
6 10 14 15 25 35

Explanation

Case 1

There is only one element, so two non-empty groups cannot be formed.

Case 2

The element $1$ must be deleted. Also, any group containing two of the other elements has gcd $1$ , so at most two elements can remain. Keeping $2$ and $3$ as two one-element groups shows that deleting five elements is sufficient.

Case 3

No deletion is needed. One valid division is $\{6,14\}$ and $\{10,15,25,35\}$ ; their gcds are $2$ and $5$ , respectively.

Output

Case 1

-1

Case 2

Case 3

You are given an array $a$ of length $n$ .

The greatest common divisor of all elements in each group must be greater than $1$ .

Find the minimum number of elements that must be deleted. If it is impossible to form such two groups, output $-1$ .

The greatest common divisor of a group containing one element is equal to that element.

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$1 \le a_i \le 2 \times 10^5$
The sum of $n$ over all test cases does not exceed $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 $7$ and $1$ . The remaining elements can be divided into $\{6,10\}$ , whose gcd is $2$ , and $\{15\}$ , whose gcd is $15$ . No valid division can keep four elements.

Delete $21$ . The other five elements can be divided into $\{6,14\}$ , whose gcd is $2$ , and $\{10,15,35\}$ , whose gcd is $5$ . It is impossible to divide all six elements validly.

No deletion is needed. One valid division is $\{6,14\}$ and $\{10,15,25,35\}$ ; their gcds are $2$ and $5$ , respectively.

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

19G. Split by GCD

Constraints

Input

Output

Samples

19G. Split by GCD

Constraints

Input

Output

Samples