H. Шесть Семь
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для положительных целых чисел $$$i$$$ и $$$j$$$ определим $$$f_i(j)$$$ как максимальное целое число $$$k$$$, такое что $$$i^k$$$ делит $$$j$$$. Число $$$j$$$ считается специальным, если $$$f_6(j) \gt f_7(j)$$$. Например, $$$6$$$ является специальным, но $$$67$$$ и $$$7$$$ не являются.

Вам дан массив $$$a$$$ из $$$n$$$ положительных целых чисел. В одной операции вы должны увеличить каждый элемент массива на $$$1$$$.

Ваша задача — найти минимальное количество операций, необходимых для того, чтобы сделать все элементы в $$$a$$$ специальными одновременно, или определить, что это невозможно.

Входные данные

Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.

Для каждого набора входных данных первая строка содержит целое число $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$).

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).

Сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число: минимальное количество операций, чтобы сделать все элементы специальными одновременно, или $$$-1$$$, если это невозможно.

Пример
Входные данные
4
3
1 2 3
2
25 67
8
6 6 12 18 24 36 42 84
1
9557351
Выходные данные
-1
5
12
7
Примечание

В первом наборе входных данных все элементы не могут быть сделаны специальными одновременно.

Во втором наборе входных данных выполнение $$$5$$$ операций приводит к массиву $$$[30,72]$$$, элементы которого все специальные.

В четвертом наборе входных данных массив становится $$$[9557358]$$$ после $$$7$$$ операций.