### 问题描述 在神秘的魔法世界中，小然是一位著名的法师。他有一个包含 $N$ 个魔法卷轴的集合 $A$，每个卷轴都有一个特定的魔法强度。然而，这些卷轴中有一些是相互冲突的，不能同时使用。卷轴的冲突性由其魔法强度的最大公约数 (gcd) 决定。如果两个卷轴的魔法强度的 gcd 大于 $1$，则它们是冲突的。 小然在冒险中经常需要使用他的魔法卷轴。每次，他都会设定一个魔法强度 $X$，然后从卷轴集合中选择一个魔法强度与 $X$ 的 gcd 大于 1 的卷轴。如果有多个卷轴满足条件，他会选择魔法强度最小的那个。在选择后，为了避免冲突，他会把这个卷轴从集合中移除。如果没有满足条件的卷轴，他则会选择魔法强度最小的卷轴，并将其从集合中移除。 你的任务是，对于小然的每一次选择，确定他会选择哪个卷轴。 ### 输入格式 输入的第一行包含一个整数 $T$，表示测试用例的数量。 每个测试用例包含多行： - 第一行包含一个整数 $N$，表示卷轴的数量。 - 第二行包含 $N$ 个空格分隔的整数 $A_1, A_2, ..., A_N$，表示每个卷轴的魔法强度。 - 第三行包含一个整数 $Q$，表示小然的选择次数。 - 第四行包含 $Q$ 个空格分隔的整数，其中第 $i$ 个整数 $X_i$ 表示小然的第 $i$ 次选择的魔法强度。 ### 输出格式 对于每个测试用例，输出一行包含 $Q$ 个空格分隔的整数，表示每次小然的选择的卷轴的魔法强度。 ### 样例输入 ```text 1 5 2 9 3 15 10 4 2 2 3 7 ``` ### 样例输出 ```text 2 10 3 9 ``` ### 说明 在第一个测试用例中，小然的卷轴集合是 $[2, 9, 3, 15, 10]$，他有 $4$ 次选择。 - 第一次，他设定的魔法强度为 $2$，可以选择的卷轴有 $2$ 和 $10$，他选择了魔法强度最小的 $2$，然后将其从集合中移除，剩下的卷轴为 $[9, 3, 15, 10]$。 - 第二次，他设定的魔法强度为 $2$，可以选择的卷轴有 $10$，他选择了魔法强度最小的 $10$，然后将其从集合中移除，剩下的卷轴为 $[9, 3, 15]$。 - 第三次，他设定的魔法强度为 $3$，可以选择的卷轴有 $3$ 和 $9$，他选择了魔法强度最小的 $3$，然后将其从集合中移除，剩下的卷轴为 $[9, 15]$。 - 第四次，他设定的魔法强度为 $7$，没有卷轴的魔法强度与 $7$ 的 gcd 大于 $1$，所以他选择了魔法强度最小的 $9$，然后将其从集合中移除，剩下的卷轴为 $[15]$。 所以，小然每次的选择分别是 $2, 10, 3, 9$。 ### 评测数据范围 $1 \leq T \leq 10^5$。 $1 \leq Q \leq N \leq 2 \cdot 10^5$。 $1 \leq A_i, X_i \leq 10^6$。 所有测试用例的 $N$ 的总和不超过 $2 \cdot 10^5$。 所有测试用例的 $Q$ 的总和不超过 $2 \cdot 10^5$。