1771C.md (1426B)
1 Source: https://codeforces.com/problemset/problem/1771/C 2 3 C. Hossam and Trainees 4 5 time limit per test 6 7 3 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Hossam has $n$ trainees. He assigned a number $a_i$ for the $i$-th trainee. 22 23 A pair of the $i$-th and $j$-th ($i \neq j$) trainees is called successful if there is an integer $x$ ($x \geq 2$), such that $x$ divides $a_i$, and $x$ divides $a_j$. 24 25 Hossam wants to know if there is a successful pair of trainees. 26 27 Hossam is very tired now, so he asks you for your help! 28 29 Input 30 31 The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^5$), the number of test cases. A description of the test cases follows. 32 33 The first line of each test case contains an integer number $n$ ($2 \le n \le 10^5$). 34 35 The second line of each test case contains $n$ integers, the number of each trainee $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$). 36 37 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$. 38 39 Output 40 41 Print the answer — "YES" (without quotes) if there is a successful pair of trainees and "NO" otherwise. You can print each letter in any case. 42 43 Example 44 45 Input 46 47 ``` 48 2 49 50 3 51 52 32 48 7 53 54 3 55 56 14 5 9 57 ``` 58 59 Output 60 61 ``` 62 YES 63 NO 64 ``` 65 66 Note 67 68 In the first example, the first trainee and the second trainee make up a successful pair: 69 70 $a_1 = 32, a_2 = 48$, you can choose $x = 4$.