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\)