Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

D. Уравняй делением
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a$$$, состоящий из $$$n$$$ целых положительных чисел. Вы можете совершать над ним операцию, состоящую из следующей последовательности действий:

  1. выбрать пару элементов $$$a_i$$$ и $$$a_j$$$ ($$$1 \le i, j \le n$$$ и $$$i \neq j$$$);
  2. выбрать один из делителей числа $$$a_i$$$, то есть число $$$x$$$ такое, что $$$a_i \bmod x = 0$$$;
  3. заменить $$$a_i$$$ на $$$\frac{a_i}{x}$$$ и $$$a_j$$$ на $$$a_j \cdot x$$$.
Определите, можно ли, применив операцию к массиву некоторое количество раз (возможно, нулевое) сделать все элементы в массиве одинаковыми?

Например, пусть дан массив $$$a$$$ = [$$$100, 2, 50, 10, 1$$$], состоящий из $$$5$$$ элементов. Произведем над ним две операции:

  1. Выберем $$$a_3 = 50$$$ и $$$a_2 = 2$$$, $$$x = 5$$$. Заменим $$$a_3$$$ на $$$\frac{a_3}{x} = \frac{50}{5} = 10$$$, $$$a_2$$$ на $$$a_2 \cdot x = 2 \cdot 5 = 10$$$. Получим массив $$$a$$$ = [$$$100, 10, 10, 10, 1$$$];
  2. Выберем $$$a_1 = 100$$$ и $$$a_5 = 1$$$, $$$x = 10$$$. Заменим $$$a_1$$$ на $$$\frac{a_1}{x} = \frac{100}{10} = 10$$$, $$$a_5$$$ на $$$a_5 \cdot x = 1 \cdot 10 = 10$$$. Получим массив $$$a$$$ = [$$$10, 10, 10, 10, 10$$$].
После выполнения данных операций все элементы массива $$$a$$$ стали равны $$$10$$$.
Входные данные

Первая строка входных данных содержит единственное число $$$t$$$ ($$$1 \le t \le 2000$$$) — количество наборов входных данных в тесте.

Далее следуют описания наборов входных данных.

Первая строка каждого набора содержит единственное целое число $$$n$$$ ($$$1 \le n \le 10^4$$$) — количество элементов в массиве $$$a$$$.

Вторая строка каждого набора содержит ровно $$$n$$$ целых чисел $$$a_i$$$ ($$$1 \le a_i \le 10^6$$$) — элементы массива $$$a$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам не превосходит $$$10^4$$$.

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

Для каждого набора входных данных в отдельной строке выведите:

  • «YES», если можно сделать элементы массива равными, применяя операцию некоторое (возможно, нулевое) количество раз;
  • «NO» в противном случае.

Вы можете выводить ответ в любом регистре (например, строки «yEs», «yes», «Yes» и «YES» будут распознаны как положительный ответ).

Пример
Входные данные
7
5
100 2 50 10 1
3
1 1 1
4
8 2 4 2
4
30 50 27 20
2
75 40
2
4 4
3
2 3 1
Выходные данные
YES
YES
NO
YES
NO
YES
NO
Примечание

Первый набор входных данных разобран в условии задачи.