B. Сбалансированные остатки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дано число $$$n$$$ (делящееся на $$$3$$$) и массив $$$a[1 \dots n]$$$. За один ход вы можете увеличить любой из элементов массива на единицу. Формально, вы выбираете индекс $$$i$$$ ($$$1 \le i \le n$$$) и заменяете $$$a_i$$$ на $$$a_i + 1$$$. Вы можете выбирать один и тот же индекс $$$i$$$ неоднократно для разных ходов.

Обозначим за $$$c_0$$$, $$$c_1$$$ и $$$c_2$$$ количества чисел из массива $$$a$$$ которые имеют остаток $$$0$$$, $$$1$$$ и $$$2$$$ при делении на число $$$3$$$ соответственно. Скажем, что массив $$$a$$$ имеет сбалансированные остатки, если $$$c_0$$$, $$$c_1$$$ и $$$c_2$$$ равны между собой.

Например, если $$$n = 6$$$ и $$$a = [0, 2, 5, 5, 4, 8]$$$, то возможна следующая последовательность ходов:

  • изначально $$$c_0 = 1$$$, $$$c_1 = 1$$$ и $$$c_2 = 4$$$, эти величины не равны между собой. Увеличим $$$a_3$$$, теперь массив $$$a = [0, 2, 6, 5, 4, 8]$$$;
  • $$$c_0 = 2$$$, $$$c_1 = 1$$$ и $$$c_2 = 3$$$, эти величины не равны между собой. Увеличим $$$a_6$$$, теперь массив $$$a = [0, 2, 6, 5, 4, 9]$$$;
  • $$$c_0 = 3$$$, $$$c_1 = 1$$$ и $$$c_2 = 2$$$, эти величины не равны между собой. Увеличим $$$a_1$$$, теперь массив $$$a = [1, 2, 6, 5, 4, 9]$$$;
  • $$$c_0 = 2$$$, $$$c_1 = 2$$$ и $$$c_2 = 2$$$, эти величины равны между собой, значит, массив $$$a$$$ имеет сбалансированные остатки.

Найдите, какое минимальное количество ходов необходимо сделать, чтобы массив $$$a$$$ имел сбалансированные остатки.

Входные данные

В первой строке содержится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$). Далее следуют $$$t$$$ наборов входных данных.

В первой строке каждого набора входных данных находится одно целое число $$$n$$$ ($$$3 \le n \le 3 \cdot 10^4$$$) — длина массива $$$a$$$. Гарантируется, что число $$$n$$$ делится на $$$3$$$.

Следующая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 100$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$150\,000$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — минимальное количество ходов, которые надо совершить, чтобы массив $$$a$$$ имел сбалансированные остатки.

Пример
Входные данные
4
6
0 2 5 5 4 8
6
2 0 2 1 0 0
9
7 1 3 4 2 10 3 9 6
6
0 1 2 3 4 5
Выходные данные
3
1
3
0
Примечание

Первый набор входных данных разобран в условии.

Во втором наборе входных данных необходимо сделать один ход для $$$i=2$$$.

В третьем наборе входных данных необходимо сделать три хода:

  • первый ход: $$$i=9$$$;
  • второй ход: $$$i=9$$$;
  • третий ход: $$$i=2$$$.

В четвертом наборе входных данных величины $$$c_0$$$, $$$c_1$$$ и $$$c_2$$$ изначально совпадают, поэтому массив $$$a$$$ уже имеет сбалансированные остатки.