Các phần tử bằng nhau

Trong một buổi thực hành, FullHouse Dev và đồng đội được giao một bài toán thú vị về xử lý mảng. Họ phải tìm cách làm cho tất cả các phần tử trong một mảng trở nên bằng nhau với chi phí tối thiểu. Với tinh thần đồng đội và sự sáng tạo, nhóm bắt đầu phân tích và giải quyết vấn đề này.

Bài toán

FullHouse Dev nhận được một mảng \(A\) gồm \(n\) phần tử nguyên. Họ có thể thực hiện hai loại thao tác trên mảng \(A\):

1. Chọn bất kỳ phần tử nào và tăng hoặc giảm nó đi 3 đơn vị với chi phí 1 đồng xu.
2. Chọn bất kỳ phần tử nào và tăng hoặc giảm nó đi 2 đơn vị mà không mất chi phí.

Nhiệm vụ của nhóm là tìm ra số đồng xu tối thiểu cần sử dụng để làm cho tất cả các phần tử trong mảng \(A\) bằng nhau.

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(T\) - số lượng test case.
• Dòng đầu tiên của mỗi test case chứa số nguyên \(n\) - số lượng phần tử trong mảng \(A\).
• Dòng thứ hai của mỗi test case chứa \(n\) số nguyên cách nhau bởi dấu cách - các phần tử của mảng \(A\).

OUTPUT FORMAT:

• In ra \(T\) dòng. Mỗi dòng chứa một số nguyên duy nhất biểu thị số đồng xu tối thiểu cần dùng để làm cho tất cả phần tử trong mảng bằng nhau.

Ràng buộc:

• \(1 \leq T \leq 10^5\)
• \(1 \leq n \leq 10^5\)
• \(1 \leq A[i] \leq 10^9\)
• Tổng của \(n\) trong tất cả các test case không vượt quá 500000

VÍ DỤ

INPUT

1
4
3 5 2 3

OUTPUT

1

Giải thích

FullHouse Dev có thể làm cho tất cả các phần tử bằng 3 với chi phí 1 đồng xu, đây là phương án tối ưu:

• Tăng 2 lên 5 với chi phí 1 đồng xu.
• Giảm cả hai số 5 xuống 3 mà không mất chi phí.