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.

brute force

greedy

math

sortings

*1000

No tag edit access

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

×
B. 378QAQ and Mocha's Array

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputMocha likes arrays, so before her departure, 378QAQ gave her an array $$$a$$$ consisting of $$$n$$$ positive integers as a gift.

Mocha thinks that $$$a$$$ is beautiful if there exist two numbers $$$i$$$ and $$$j$$$ ($$$1\leq i,j\leq n$$$, $$$i\neq j$$$) such that for all $$$k$$$ ($$$1 \leq k \leq n$$$), $$$a_k$$$ is divisible$$$^\dagger$$$ by either $$$a_i$$$ or $$$a_j$$$.

Determine whether $$$a$$$ is beautiful.

$$$^\dagger$$$ $$$x$$$ is divisible by $$$y$$$ if there exists an integer $$$z$$$ such that $$$x = y \cdot z$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1\leq t\leq 500$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$3\leq n\leq 10^5$$$) — the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1\leq a_i \leq 10^9$$$) — the elements of the array $$$a$$$.

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

Output

For each test case, output "Yes" if array $$$a$$$ is beautiful, and output "No" otherwise.

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

Example

Input

437 3 857 1 9 3 554 12 2 6 357 49 9 3 1000000000

Output

No Yes Yes No

Note

In the first test case, any two numbers in the array are coprime, so the answer is "No".

In the second test case, we can pick $$$i=2$$$ and $$$j=1$$$. Since every number in the array is divisible by $$$a_i = 1$$$, the answer is "Yes".

In the third test case, we can pick $$$i=3$$$ and $$$j=5$$$. $$$2$$$ and $$$4$$$ is divisible by $$$a_i = 2$$$ while $$$3$$$, $$$6$$$ and $$$12$$$ is divisible by $$$a_j = 3$$$, so the answer is "Yes".

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/25/2024 14:17:20 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|