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

$ curl repovive.com/contests/19/problems/G

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

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.

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

19G. Split by GCD

Constraints

Input

Output

Samples

19G. Split by GCD

Constraints

Input

Output

Samples