311365: CF1975B. 378QAQ and Mocha's Array

B. 378QAQ and Mocha's Arraytime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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

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).

ExampleInput

4
3
7 3 8
5
7 1 9 3 5
5
4 12 2 6 3
5
7 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".

题目大意：
378QAQ给Mocha一个由n个正整数组成的数组a作为礼物。如果存在两个数i和j（1≤i,j≤n，i≠j），使得对于所有的k（1≤k≤n），ak能被ai或aj整除，则称a是“美丽”的。确定数组a是否美丽。

输入数据格式：
每个测试包含多个测试案例。第一行包含测试案例数t（1≤t≤500）。接下来是每个测试案例的描述。
每个测试案例的第一行包含一个整数n（3≤n≤10^5）——数组a的长度。
第二行包含n个整数a1,a2,…,an（1≤ai≤10^9）——数组a的元素。
保证所有测试案例的n之和不超过10^5。

输出数据格式：
对于每个测试案例，如果数组a是美丽的，输出"Yes"，否则输出"No"。
"Yes"和"No"的大小写不敏感。

示例：
输入
```
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
```

注意：
- 在第一个测试案例中，数组中的任意两个数都是互质的，所以答案是"No"。
- 在第二个测试案例中，我们可以选择i=2和j=1。由于数组中的每个数都能被ai=1整除，所以答案是"Yes"。
- 在第三个测试案例中，我们可以选择i=3和j=5。2和4能被ai=2整除，而3、6和12能被aj=3整除，所以答案是"Yes"。题目大意： 378QAQ给Mocha一个由n个正整数组成的数组a作为礼物。如果存在两个数i和j（1≤i,j≤n，i≠j），使得对于所有的k（1≤k≤n），ak能被ai或aj整除，则称a是“美丽”的。确定数组a是否美丽。 输入数据格式： 每个测试包含多个测试案例。第一行包含测试案例数t（1≤t≤500）。接下来是每个测试案例的描述。 每个测试案例的第一行包含一个整数n（3≤n≤10^5）——数组a的长度。 第二行包含n个整数a1,a2,…,an（1≤ai≤10^9）——数组a的元素。 保证所有测试案例的n之和不超过10^5。 输出数据格式： 对于每个测试案例，如果数组a是美丽的，输出"Yes"，否则输出"No"。 "Yes"和"No"的大小写不敏感。 示例： 输入 ``` 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 ``` 注意： - 在第一个测试案例中，数组中的任意两个数都是互质的，所以答案是"No"。 - 在第二个测试案例中，我们可以选择i=2和j=1。由于数组中的每个数都能被ai=1整除，所以答案是"Yes"。 - 在第三个测试案例中，我们可以选择i=3和j=5。2和4能被ai=2整除，而3、6和12能被aj=3整除，所以答案是"Yes"。