题目描述

Mocha 喜欢数组，所以在她离开之前，378QAQ 送给了她一个由 $n$ 个正整数组成的数组 $a$ 作为礼物。

Mocha 认为数组 $a$ 是“美丽的”，如果存在两个数 $i$ 和 $j$（$1 \leq i, j \leq n$，$i \neq j$），使得对于所有 $k$（$1 \leq k \leq n$），$a_k$ 都能被 $a_i$ 或 $a_j$ 整除$^\dagger$。

请判断数组 $a$ 是否“美丽”。

$^\dagger$ 如果存在一个整数 $z$ 使得 $x = y \cdot z$，则称 $x$ 能被 $y$ 整除。

输入格式

每个测试点包含多组测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 500$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$3 \leq n \leq 10^5$），表示数组 $a$ 的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$），表示数组 $a$ 的元素。

保证所有测试用例中 $n$ 的总和不超过 $10^5$。

输出格式

对于每个测试用例，如果数组 $a$ 是“美丽的”，输出 "Yes"；否则输出 "No"。

你可以以任意大小写输出 "Yes" 和 "No"（例如 "yEs"、"yes"、"Yes" 和 "YES" 都会被识别为肯定回答）。

说明/提示

在第一个测试用例中，数组中的任意两个数都是互质的，所以答案是 "No"。

在第二个测试用例中，我们可以选择 $i=2$ 和 $j=1$。由于数组中的每个数都能被 $a_i=1$ 整除，所以答案是 "Yes"。

在第三个测试用例中，我们可以选择 $i=3$ 和 $j=5$。$2$ 和 $4$ 能被 $a_i=2$ 整除，而 $3$、$6$ 和 $12$ 能被 $a_j=3$ 整除，所以答案是 "Yes"。

由 ChatGPT 4.1 翻译

样例

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