CF2065G Skibidus and Capping

Skibidus was abducted by aliens of Amog! Skibidus tries to talk his way out, but the Amog aliens don't believe him. To prove that he is not totally capping, the Amog aliens asked him to solve this task: An integer $ x $ is considered a semi-prime if it can be written as $ p \cdot q $ where $ p $ and $ q $ are (not necessarily distinct) [prime numbers](https://en.wikipedia.org/wiki/Prime_number). For example, $ 9 $ is a semi-prime since it can be written as $ 3 \cdot 3 $ , and $ 3 $ is a prime number. Skibidus was given an array $ a $ containing $ n $ integers. He must report the number of pairs $ (i, j) $ such that $ i \leq j $ and $ \operatorname{lcm}(a_i, a_j) $ $ ^{\text{∗}} $ is semi-prime. $ ^{\text{∗}} $ Given two integers $ x $ and $ y $ , $ \operatorname{lcm}(x, y) $ denotes the [least common multiple](https://en.wikipedia.org/wiki/Least_common_multiple) of $ x $ and $ y $ .

The first line contains an integer $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases. The first line of each test case contains an integer $ n $ ( $ 2 \leq n \leq 2 \cdot 10^5 $ ). The following line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 2 \leq a_i \leq n $ ). It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

For each test case, output the number of ordered pairs of indices on a new line.

In the first test case, the $ 5 $ pairs of indices are $ (1, 3) $ , $ (1, 4) $ , $ (2, 3) $ , $ (2, 4) $ , and $ (4, 4) $ .