今天,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$$$。
示例
输入复制
683 2 2 3 7 3 6 751 2 3 4 531 1 1102 1 2 1 3 5 5 7 7 741 1 2 211
输出复制
-1 1 1 2 -1 1 1 31 1 1 1 11 -1 -11 1 1 2 1 2 1 3 2 21 1 -1 21
注意
考虑第一个测试用例。产品可通过以下方式获得:
- 无法获取$$$1$$$。
- $$$2$$$可以通过选择$$$a_2$$$获得。
- $$$3$$$可以通过选择$$$a_1$$$获得。
- $$$4$$$可以通过选择$$$a_2$$$两次获得。
- 无法获取$$$5$$$。
- $$$6$$$可以通过选择$$$a_7$$$获得。
- $$$7$$$可以通过选择$$$a_5$$$获得。
- $$$8$$$可以通过选择$$$a_2$$$ 3次获得。