E. Запросы произведения
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Сегодня Сабыржану выписали на доску массив $$$a$$$ длины $$$n$$$ и поручили офицерское задание — ответить на $$$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$$$ три раза.