Statement

Mocha 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$ .

Format

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.

Sample

4
3
7 3 8
5
7 1 9 3 5
5
4 12 2 6 3
5
7 49 9 3 1000000000

No
Yes
Yes
No