CF1630F.Making It Bipartite

You are given an undirected graph of $n$ vertices indexed from $1$ to $n$, where vertex $i$ has a value $a_i$ assigned to it and all values $a_i$ are different. There is an edge between two vertices $u$ and $v$ if either $a_u$ divides $a_v$ or $a_v$ divides $a_u$.

Find the minimum number of vertices to remove such that the remaining graph is bipartite, when you remove a vertex you remove all the edges incident to it.

给你一个包含 $n$ 个顶点的无向图，顶点编号从 $1$ 到 $n$。每个顶点 $i$ 被赋予一个值 $a_i$，且所有 $a_i$ 互不相同。当且仅当 $a_u$ 整除 $a_v$ 或 $a_v$ 整除 $a_u$ 时，顶点 $u$ 和 $v$ 之间存在一条边。

求最少需要删除多少个顶点，才能使得剩余图是二分图；删除一个顶点的同时，也将与其关联的所有边一并删除。

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 5\cdot10^4$) — the number of vertices in the graph.

The second line of each test case contains $n$ integers, the $i$-th of them is the value $a_i$ ($1 \le a_i \le 5\cdot10^4$) assigned to the $i$-th vertex, all values $a_i$ are different.

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

输入包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 5\cdot10^4$），表示图中顶点的数量。

每个测试用例的第二行包含 $n$ 个整数，其中第 $i$ 个整数为分配给第 $i$ 个顶点的值 $a_i$（$1 \le a_i \le 5\cdot10^4$），所有 $a_i$ 的值互不相同。

保证所有测试用例的 $n$ 值之和不超过 $5\cdot10^4$。

For each test case print a single integer — the minimum number of vertices to remove such that the remaining graph is bipartite.

对于每个测试用例，输出一个整数——使得剩余图是二分图所需删除的最少顶点数。

In the first test case if we remove the vertices with values $1$ and $2$ we will obtain a bipartite graph, so the answer is $2$, it is impossible to remove less than $2$ vertices and still obtain a bipartite graph.

Before

After

test case #1

In the second test case we do not have to remove any vertex because the graph is already bipartite, so the answer is $0$.

Before

After

test case #2

In the third test case we only have to remove the vertex with value $12$, so the answer is $1$.

Before

After

test case #3

In the fourth test case we remove the vertices with values $2$ and $195$, so the answer is $2$.

Before

After

test case #4

在第一个测试用例中，如果我们删除值为 $1$ 和 $2$ 的顶点，则会得到一个二分图，因此答案是 $2$；不可能仅删除少于 $2$ 个顶点就仍得到一个二分图。

删除前

删除后

测试用例 #1

在第二个测试用例中，我们无需删除任何顶点，因为该图本身已是二分图，因此答案是 $0$。

删除前

删除后

测试用例 #2

在第三个测试用例中，我们只需删除值为 $12$ 的顶点，因此答案是 $1$。

删除前

删除后

测试用例 #3

在第四个测试用例中，我们删除值为 $2$ 和 $195$ 的顶点，因此答案是 $2$。

删除前

删除后

测试用例 #4