G. Skibidus and Capping
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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. 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 of $$$x$$$ and $$$y$$$.

Input

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$$$.

Output

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

Example
Input
3
4
2 2 3 4
6
2 2 3 4 5 6
9
2 2 4 5 7 8 9 3 5
Output
5
12
18
Note

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