You are given an array $A$ having $N$ integers. Find the number of triplets $(i, j, k)$ such that 

• $1 \le i \lt j \lt k \le N$.
• $A_i \times A_j \times A_k$ is Prime number.

Input format

• The first line of input contains an integer $T$ denoting the number of test cases. The description of each test case is as follows:
• The first line of each test case contains an integers $N$.
• The second line of each test case contains $N$ integers $A_1, A_2,\dots, A_N$.

Output format

For each test case, print the number of triplets that satisfies the given conditions in a separate line.

Constraints

$1\le T \le 10 \\ 3 \leq N \le 10^5\\ 1\le A_i \le 10^5$