Cho số nguyên dương \(N\) và dãy số nguyên \(A_1,A_2,..,A_N\). Tính số lượng bộ ba \((i,j,k)\) sao cho: 1 ≤ i < j < k ≤ N; và \(A_i × A_j × A_k\) là số nguyên tố.

Input:

• Dòng đầu tiên chứ số nguyên \(T (1≤T≤10)\) – là số bộ Test, với mỗi bộ Test

• Dòng 1: chứa hai số nguyên \(N (3 ≤ N ≤ 10^5 )\);

• Dòng 2: chứa n số nguyên \(A_1,A_2,…,A_N (1≤A_i ≤ 10^5 )\);

Output:

• Kết quả mỗi Test ghi trên một dòng là số bộ ba tìm được.

Sample Input

2
4
4 5 6 2
4
1 1 4 5

Sample Output

0 
1

Ràng buộc

• Subtask 1: \(N ≤ 1000\)

• Sbtask 2: \(N ≤ 100000\)