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.

Note

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

Skibidus and Capping

Examples