Hôm nay các bạn học sinh được thầy giáo dạy về số chính phương, sau đó thầy giáo giao bài tập cho các bạn học sinh như sau. Thầy giáo đưa cho một dãy số gồm N số nguyên A₁, A₂, A₃, ... , A_N. Thầy hỏi, liệu có bao nhiêu cặp số (a, b) sao cho 1≤a < b≤N và A_a * A_b là một số chính phương. Vì dãy có nhiều số quá nên các bạn học sinh không thể đếm được.

Hãy giúp các bạn học sinh đếm xem có bao nhiêu cặp số thỏa mãn yêu cầu của thầy giáo nhé !

Input

• Dòng đầu tiên chứa số nguyên T (1≤T≤10) là số lượng thử nghiệm.
• Trong mỗi bộ thử nghiệm, dòng đầu tiên gồm một số nguyên dương N (1≤N≤10⁵), dòng thứ hai gồm dãy số nguyên A₁, A₂, A₃, ... , A_N (1≤A_i≤10⁶).

Output

• Gồm T dòng, mỗi dòng gồm một số nguyên duy nhất là số lượng cặp (a, b) thỏa mãn yêu cầu của thầy giáo, thứ tự của đáp án tương ứng với thứ tự đầu vào của bộ thử nghiệm.

Scoring

• Có 50% số điểm ứng với 1≤N≤1000.
• Có 50% số điểm còn lại không có ràng buộc gì thêm.

Example

input
1
5
1 2 3 4 5

output
1