Codeforces Round 903 (Div. 3) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

math

number theory

*1300

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Divide and Equalize

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou are given an array $$$a$$$ consisting of $$$n$$$ positive integers. You can perform the following operation on it:

- Choose a pair of elements $$$a_i$$$ and $$$a_j$$$ ($$$1 \le i, j \le n$$$ and $$$i \neq j$$$);
- Choose one of the divisors of the integer $$$a_i$$$, i.e., an integer $$$x$$$ such that $$$a_i \bmod x = 0$$$;
- Replace $$$a_i$$$ with $$$\frac{a_i}{x}$$$ and $$$a_j$$$ with $$$a_j \cdot x$$$.

For example, let's consider the array $$$a$$$ = [$$$100, 2, 50, 10, 1$$$] with $$$5$$$ elements. Perform two operations on it:

- Choose $$$a_3 = 50$$$ and $$$a_2 = 2$$$, $$$x = 5$$$. Replace $$$a_3$$$ with $$$\frac{a_3}{x} = \frac{50}{5} = 10$$$, and $$$a_2$$$ with $$$a_2 \cdot x = 2 \cdot 5 = 10$$$. The resulting array is $$$a$$$ = [$$$100, 10, 10, 10, 1$$$];
- Choose $$$a_1 = 100$$$ and $$$a_5 = 1$$$, $$$x = 10$$$. Replace $$$a_1$$$ with $$$\frac{a_1}{x} = \frac{100}{10} = 10$$$, and $$$a_5$$$ with $$$a_5 \cdot x = 1 \cdot 10 = 10$$$. The resulting array is $$$a$$$ = [$$$10, 10, 10, 10, 10$$$].

Input

The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 2000$$$) — the number of test cases.

Then follows the description of each test case.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^4$$$) — the number of elements in the array $$$a$$$.

The second line of each test case contains exactly $$$n$$$ integers $$$a_i$$$ ($$$1 \le a_i \le 10^6$$$) — the elements of the array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^4$$$.

Output

For each test case, output a single line:

- "YES" if it is possible to make all elements in the array equal by applying the operation a certain (possibly zero) number of times;
- "NO" otherwise.

You can output the answer in any case (for example, the strings "yEs", "yes", "Yes", and "YES" will all be recognized as a positive answer).

Example

Input

75100 2 50 10 131 1 148 2 4 2430 50 27 20275 4024 432 3 1

Output

YES YES NO YES NO YES NO

Note

The first test case is explained in the problem statement.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/11/2023 09:12:30 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|