CF2193E.Product Queries

Today, Sabyrzhan was called to the board with an array $a$ of length $n$ and was assigned an officer's task — to answer $n$ questions.

In the $i$-th question, it is required to determine the minimum number of elements from the array that need to be selected from the board (it is allowed to use the same element multiple times) so that their product is exactly equal to $i$, or to report that it is impossible to achieve such a product.

Note that at least one element must be selected.

今天，萨比尔江被叫到黑板前，面对一个长度为 $n$ 的数组 $a$，并被布置了一项“军官任务”——回答 $n$ 个问题。

在第 $i$ 个问题中，需要确定：从该数组中至少选取多少个元素（允许重复选取同一元素），使得它们的乘积恰好等于 $i$；若无法实现这样的乘积，则报告“不可能”。

注意：必须至少选取一个元素。

Each test consists of several test cases. The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains one integer $n$ ($1 \le n \le 3 \cdot 10 ^ 5$).

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$).

It is guaranteed that the sum of the values of $n$ across all test cases does not exceed $3 \cdot 10 ^ 5$.

每个测试包含若干测试用例。第一行包含一个整数 $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$。

For the $i$-th question, output one integer — the minimum number of elements from the array required to obtain a product equal to $i$, or $−1$ if it is impossible to achieve such a product.

对于第 $i$ 个问题，输出一个整数——为得到乘积恰好等于 $i$ 所需的数组中元素的最少个数；若无法得到该乘积，则输出 $-1$。

Consider the first test case. The products can be obtained as follows:

• $1$ cannot be obtained.
• $2$ can be obtained by selecting $a_2$.
• $3$ can be obtained by selecting $a_1$.
• $4$ can be obtained by selecting $a_2$ twice.
• $5$ cannot be obtained.
• $6$ can be obtained by selecting $a_7$.
• $7$ can be obtained by selecting $a_5$.
• $8$ can be obtained by selecting $a_2$ three times.

考虑第一个测试用例。这些乘积可以如下得到：

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