Cho một mảng \(A\) gồm \(n\) số nguyên khác nhau. Tìm số lượng bộ ba "hòa hợp" được tạo nên từ mảng \(A\).

Biết rằng, một bộ ba \((a,b,c)\) được gọi là "hòa hợp" nếu chúng khác nhau từng đôi một và thỏa mãn \(1\) trong \(2\) điều kiện sau:

• \(a,b,c\) nguyên tố cùng nhau từng đôi một

• \(a,b,c\) không nguyên tố cùng nhau từng đôi một

(Hai bộ \(A\) và \(B\) được coi là khác nhau nếu tồn tại phần tử \(k\) thỏa mãn \(k\in A\) và \(k\notin B\))

Ghi chú: Hai số \(x,y\) được coi là nguyên tố cùng nhau nếu ước chung lớn nhất của chúng là \(1\)

Input

• Dòng thứ nhất chứa số nguyên \(T(1\le T\le 15)\) - số lượng testcase.

• \(T\) block tiếp theo, mỗi block có dạng:

• Dòng thứ nhất chứa số nguyên \(n(3\le n\le 1000)\)

• Dòng thứ hai chứa số \(n\) số nguyên \(a_1,a_2,..,a_n(2\le a_i<10^5)\) khác nhau

Output

• Ứng với mỗi testcase, in ra đáp án cần tìm.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(1\le n\le 20\)

• Subtask \(2\) (\(60\%\) số điểm): Còn lại

Example

2
3
2 3 6
3
2 3 5

0
1