Trùng Khánh là một địa điểm nổi tiếng về kiến trúc đa tầng vô cùng độc đáo.

Được coi là thành phố có độ cân bằng chung giữa các công trình tiệm cận với sự hoàn hảo, nơi đây có n tòa nhà, tòa nhà thứ 1 ≤ i ≤ n có độ cân bằng là a[i], độ cân bằng k của thành phố được tính bằng tổng độ cân bằng của cả thành phố trên số lượng tòa nhà( k có thể không phải số nguyên).

Hàng năm, để có thể nâng cấp thành phố, bộ xây dựng cần tìm 2 tòa nhà để đập đi nhằm xây dựng những tòa nhà đẹp hơn, tuy kế hoạch là vậy nhưng độ cân bằng của thành phố hiện tại vẫn là bài toán khó cản trở kế hoạch cải tạo thành phố của đội ngũ xây dựng~~.

Các kỹ sư cntt của KIT trong chuyến vi hành ở Trùng Khánh đã nghe tới vấn đề này và được đề nghị giúp đỡ. Hãy tính xem liệu trong thành phố có bao nhiêu cặp 2 tòa công trình có thể xóa bỏ mà độ cân bằng của n-2 tòa nhà vẫn bằng k.

Input

Dòng đầu tiên chứa một số nguyên t(1 ≤ t  ≤ 10⁴) - số lượng testcase.

Dòng đầu tiên của mỗi test chứa một số nguyên n(3 ≤ n ≤ 2.10⁵) - số phần tử trong mảng.

Dòng thứ hai chứa dãy số nguyên a₁,a₂,…,a_n(0 ≤ a_i ≤ 10⁹), a_i là độ cân bằng của tòa nhà thứ i của thành phố.

Tổng của n ở tất cả các testcase không vượt quá 2.10⁵.

Output

Một số nguyên ứng với mỗi testcase là tổng số cặp 2 tòa nhà có thể loại bỏ mà không ảnh hưởng tới độ cân bằng của tòa thành phố.

Example

Input:
4
4
8 8 8 8
3
50 20 10
5
1 4 7 3 5
7
1 2 3 4 5 6 7

Output:
6
0
2
3

Testcase đầu tiên, bất kỳ cặp phần tử nào cũng có thể bị loại bỏ vì tất cả chúng đều bằng nhau.

Testcase thứ 2, không có cách nào để xóa hai phần tử mà giá trị trung bình toán học không thay đổi.

Testcase thứ 3, có 2 cặp có thể xóa là các cặp phần tử ở vị trí 1 và 3, hoặc các phần tử ở vị trí 4 và 5.