CF2193E Product Queries

今天，Sabyrzhan 被叫到黑板前，面对一个长度为 $ n $ 的数组 $ a $，并被布置了一项任务——回答 $ n $ 个问题。 在第 $ i $ 个问题中，需要确定从黑板上最少选择多少个数组元素（允许重复使用同一个元素），使得它们的乘积恰好等于 $ i $，或者报告无法达到这样的乘积。 注意：至少必须选择一个元素。

每个测试包含多个测试用例。第一行包含一个整数 $ t $（$ 1 \le t \le 10^4 $）——测试用例的数量。接下来是测试用例的描述。 每个测试用例的第一行包含一个整数 $ n $（$ 1 \le n \le 3 \cdot 10 ^ 5 $）。 每个测试用例的第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $（$ 1 \le a_i \le n $）。 保证所有测试用例中 $ n $ 的总和不超过 $ 3 \cdot 10 ^ 5 $。

对于第 $ i $ 个问题，输出一个整数——为获得乘积等于 $ i $ 所需的最少数组元素数量，如果无法达到这样的乘积，则输出 $ −1 $。

考虑第一个测试用例。乘积可以按如下方式获得： - $ 1 $ 无法获得。 - $ 2 $ 可以通过选择 $ a_2 $ 获得。 - $ 3 $ 可以通过选择 $ a_1 $ 获得。 - $ 4 $ 可以通过选择 $ a_2 $ 两次获得。 - $ 5 $ 无法获得。 - $ 6 $ 可以通过选择 $ a_7 $ 获得。 - $ 7 $ 可以通过选择 $ a_5 $ 获得。 - $ 8 $ 可以通过选择 $ a_2 $ 三次获得。 由 deepseek v3 翻译完成