You are given an integer array \(A\) consisting of \(N\) elements. You can perform the following operations on array \(A\):

• Choose any element and increase or decrease it by 3 for 1 coin.
• Choose any element and increase or decrease it by 2 for free.

You are required to spend the minimum number of coins in order to make all the elements in array \(A\) equal.

Input format

• The first line contains an integer \(T\) denoting the number of test cases. 
• The first line of each test case contains an integer \(N\) denoting the number of elements in array \(A\).
• The second line of each test case contains \(N\) space-separated integers of array \(A\).

Output format

Print \(T\) lines. For each test case, print a single line denoting the minimum number of coins to make all elements equal.

Constraints

\(1 \leq T \leq 20000\)

\(1 \leq N \leq 100000\)

\(1 \leq A_i \leq 10^9 \forall i \in [1,N]\)

Sum of \(N\) over all test cases does not exceed 500000