题目内容

小蓝有 $n$ 张卡片，第 $i$ 张卡片上写有一个正整数 $a_i$。他可以任意次执行以下操作：选择两张不同的卡片 $i$ 和 $j$，并选择一个大于 $1$ 的整数 $d$，满足 $d$ 同时整除 $a_i$ 和 $a_j$，然后将 $a_i$ 和 $a_j$ 都除以 $d$。小蓝想知道，通过有限次操作，能否使所有卡片上的数字都变为 $1$。

测试数据包含多组，组数 $T$ 不超过 $2 \times 10^5$。每组数据中，卡片数量 $n$ 不超过 $2 \times 10^5$，且所有测试数据的 $n$ 之和也不超过 $2 \times 10^5$。每张卡片上的整数 $a_i$ 满足 $1 \le a_i \le 2 \times 10^5$。

输入描述

第一行输入一个整数 T，表示测试数据组数。接下来依次描述每组测试数据： 对于每组测试数据，第一行输入一个整数 n，表示卡片数量； 第二行输入 n 个整数，表示每张卡片上的初始数字。