Random
题号:NC312172
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

\hspace{15pt}小红拿到了一个长为 n 的数组 a_1, a_2, \ldots, a_n。她想要选择其中两个不同位置的元素,要求这两个元素的最大公约数大于 1,请你帮帮她。
\hspace{15pt}特殊的,保证数组元素在 [1, 10^9] 范围内独立均匀随机生成

【名词解释】
\hspace{15pt}最大公约数(gcd):指两个或多个整数共有约数中最大的一个。例如,1230 的公约数有 1,2,3,6,其中最大的约数是 6,因此记作 \gcd(12,30)=6

输入描述:

\hspace{15pt}每个测试文件均包含多组测试数据。第一行输入一个整数 T\left(1\leqq T\leqq 10^4\right) 代表数据组数,每组测试数据描述如下:

\hspace{15pt}第一行输入一个整数 n \left(1 \leqq n \leqq 2\times 10^5 \right),代表数组长度。
\hspace{15pt}第二行输入 n 个整数 a_1, a_2, \ldots, a_n \left(1 \leqq a_i \leqq 10^9 \right),代表数组元素。

\hspace{15pt}除此之外,保证单个测试文件的 n 之和不超过 2 \times 10^5

输出描述:

\hspace{15pt}对于每组测试数据,如果不存在符合要求的两个元素,直接输出 -1;否则,在一行上输出两个整数,代表选中的两个元素的值。

\hspace{15pt}如果存在多个解决方案,您可以输出任意一个,系统会自动判定是否正确。注意,自测运行功能可能因此返回错误结果,请自行检查答案正确性。
示例1

输入

复制
2
5
101770993 7791101 39239295 480041099 460611962
5
981262894 280102212 13579679 112334424 10169419

输出

复制
-1
981262894 280102212

备注:

\hspace{15pt}在几乎全部的情况下,PyPy 的运行速度优于 Python,我们建议您选择对应版本的 PyPy 进行提交、而不是 Python。