Cặp Số Tốt

Bối cảnh

FullHouse Dev cần giải quyết một bài toán như sau:

Yêu cầu

Cho một mảng số nguyên dương \( A \) có độ dài \( N \).

Một cặp \( (i, j) \) \((1 \leq i < j \leq N)\) được gọi là cặp tốt nếu Ước Chung Lớn Nhất (ƯCLN) của \( A_i \) và \( A_j \) bằng với Bội Chung Nhỏ Nhất (BCNN) của chúng. Cụ thể:

\(\text{gcd}(A_i, A_j) = \text{lcm}(A_i, A_j)\)

Trong đó:

• \(\text{gcd}(x, y)\) là Ước Chung Lớn Nhất của \( x \) và \( y \).
• \(\text{lcm}(x, y)\) là Bội Chung Nhỏ Nhất của \( x \) và \( y \).

Nhiệm vụ của bạn là tìm tổng số cặp tốt có trong mảng đã cho.

Input

• Dòng đầu tiên chứa một số nguyên \( T \) - số lượng bộ test.
• Mỗi bộ test bắt đầu bằng một số nguyên \( N \) - độ dài của mảng \( A \).
• Dòng tiếp theo chứa \( N \) số nguyên \( A_1, A_2, \ldots, A_N \).

Output

Với mỗi bộ test, in ra một dòng chứa tổng số cặp tốt có thể có trong mảng đã cho.

Ràng buộc

• \( 1 \leq T \leq 100 \)
• \( 1 \leq N \leq 10^5 \)
• \( 1 \leq A_i \leq 10^9 \)
• Tổng của tất cả các \( N \) trong tất cả các bộ test không vượt quá \( 3 \cdot 10^5 \).

Ví dụ 1

Input

5
2
5 9
5
1 5 5 5 9
8
2 5 5 2 9 9 9 12
4
12 12 18 18
5
12 15 10 5 9

Output

0
3
5
2
0

Giải thích ví dụ

• Test case 1: Không có cặp tốt nào.

• Test case 2: Các cặp tốt là: \( (2, 3), (3, 4), (2, 4) \). Chi tiết: \(\text{gcd}(A_2, A_3) = \text{lcm}(A_2, A_3) = 5\).

• Test case 3: Các cặp tốt là: \( (1, 4), (2, 3), (5, 6), (6, 7), (5, 7) \). Chi tiết: \(\text{gcd}(A_1, A_4) = \text{lcm}(A_1, A_4) = 2\).

• Test case 4: Các cặp tốt là: \( (1, 2), (3, 4) \). Chi tiết: \(\text{gcd}(A_3, A_4) = \text{lcm}(A_3, A_4) = 18\).

• Test case 5: Không có cặp tốt nào.

Thông tin học tập

• Buổi: B15
• Concepts: map, frequency counting, gcd/lcm
• Giới hạn kiến thức: B01-B15
• Time limit: 2 seconds
• Memory limit: 64 MB
• Point: 20