题目描述

今天，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$。

样例

6
8
3 2 2 3 7 3 6 7
5
1 2 3 4 5
3
1 1 1
10
2 1 2 1 3 5 5 7 7 7
4
1 1 2 2
1
1

-1 1 1 2 -1 1 1 3
1 1 1 1 1
1 -1 -1
1 1 1 2 1 2 1 3 2 2
1 1 -1 2
1

样例说明

考虑第一个测试用例。乘积可以按如下方式获得：

• $1$ 无法获得。
• $2$ 可以通过选择 $a_2$ 获得。
• $3$ 可以通过选择 $a_1$ 获得。
• $4$ 可以通过选择 $a_2$ 两次获得。
• $5$ 无法获得。
• $6$ 可以通过选择 $a_7$ 获得。
• $7$ 可以通过选择 $a_5$ 获得。
• $8$ 可以通过选择 $a_2$ 三次获得。

由 deepseek v3 翻译完成

来源

Codeforces 2193E，英文题名 Product Queries。