Making It Bipartite

题意翻译

图上有 $n$ 个点，点有点权，点权互不相同，如果两个点点权成倍数关系，那么他们有边。 现在希望删去一些点，来使图变成二分图，求出最少删去多少点。

题目描述

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.

输入输出格式

输入格式

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 $ .

输出格式

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

输入输出样例

输入样例 #1

4
4
8 4 2 1
4
30 2 3 5
5
12 4 6 2 3
10
85 195 5 39 3 13 266 154 14 2

输出样例 #1

2
0
1
2

说明

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. BeforeAftertest case #1In the second test case we do not have to remove any vertex because the graph is already bipartite, so the answer is $ 0 $ . BeforeAftertest case #2In the third test case we only have to remove the vertex with value $ 12 $ , so the answer is $ 1 $ . BeforeAftertest case #3In the fourth test case we remove the vertices with values $ 2 $ and $ 195 $ , so the answer is $ 2 $ . BeforeAftertest case #4

题意翻译

图上有 $n$ 个点，点有点权，点权互不相同，如果两个点点权成倍数关系，那么他们有边。 现在希望删去一些点，来使图变成二分图，求出最少删去多少点。