Cho \(n\) thanh gỗ và chiều dài của chúng. Thanh gỗ thứ \(i\) có chiều dài \(2^{a_i}\). Cần chọn ra 3 thanh gỗ để xếp thành tam giác có diện tích lớn hơn \(0\) với \(3\) cạnh là \(3\) thanh gỗ đã chọn. Hỏi có tất cả bao nhiêu cách chọn?

Ghi chú: Thứ tự chọn các thanh gỗ không quan trọng. Ví dụ, việc chọn thanh gỗ thứ 1, thứ 2, thứ 4 hoàn toàn giống việc chọn thanh gỗ thứ 2, thứ 4, thứ 1.

Input

Dòng đầu tiên là số bộ test \(t\) và \(2 \times t\) dòng tiếp theo mô tả \(t\) bộ test. Mỗi bộ test gồm có 2 dòng.

• Dòng đầu là số \(n\).
• Dòng sau gồm \(n\) số nguyên từ \(a_1\) đến \(a_n\) cách nhau bởi khoảng trắng.

Output

• Với mỗi bộ test, output trên 1 dòng riêng biệt kết quả tính được.

Constraints

• \(1 \le t \le 10^4\)
• \(1 \le n \le 3.10^5\)
• \(0 \le a_i \le n\)
• Tổng của \(n\) của tất cả bộ test không vượt quá \(3.10^5\)

Example

Sample input

4
7
1 1 1 1 1 1 1
4
3 2 1 3
3
1 2 3
1
1

Sample output

35
2
0
0