该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

背景

小鳄鱼最近遇到了有关min和有关gcd的问题， 但是他不知道该先做哪个。小孩子才做选择，聪明的你可以直接解决同时有关min和gcd的问题。

描述

给你一个长度为 n 的数组 a 。请判断通过重新排列数组 a 使得存在一个满足以下条件的整数 i ( 1≤i<n ) min（[$a_{1}$,$a_{2}$...$a_{i}$ ]）= gcd（[$a_{i+1}$,$a_{i+2}$...$a_{n}$]）.

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 t ( 1≤t≤1e4 )。测试用例说明如下。

每个测试用例的第一行包含一个整数 n ( 2≤n≤1e5 )。

第二行包含 n 个整数,数组a的元素 ( 1≤$a_{i}$≤1e18 )。

保证所有测试用例中 n 的总和不超过 1e5 。

输出

对于每个测试用例，如果可能，则输出 "Yes"，否则输出 "No"。

样例

7
2
1 1
2
1 2
3
2 2 3
3
2 3 4
5
4 5 6 9 3
3
998244359987710471 99824435698771045 1000000007
6
1 1 4 5 1 4

Yes
No
Yes
No
Yes
Yes
Yes

限制

1s, 1024KiB for each test case.