マルチテストについての説明はこちら (サンプル問題を確認されていない方のみお読みください。)

配点：$100$ 点

問題文

$N$ 個の整数 $A_1, A_2, \ldots, A_N$ に対して以下の操作を行うことができます：

操作：

• $1 \leq i \leq N$ を満たす整数 $i$ を選び，以下のうちいずれかを行う：
  • $A_i$ の値を $1$ だけ増加させる．
  • $A_i$ の値を $1$ だけ減少させる．

操作は $0$ 回以上好きなだけ行うことができます．

MojaMoja 君は $3$ の倍数が好きなので，操作を繰り返し行って $N$ 個の整数すべてが $3$ の倍数であるようにしたいです．

これを達成するために必要な操作の回数の最小値を求めてください．

ただし，整数 $x$ が $3$ の倍数であるとき，ある整数 $k$ が存在して $x = 3k$ を満たします．

制約

• $1 \leq \Phi \leq 10^5$
• $1 \leq N$
• $\sum_{\phi} \Phi_{\phi}(N) \leq 10^5$
• $|A_i| < 2^{30} \; \scriptsize(1 \leq i \leq N)$
• 入力はすべて整数

入力

各テストケースの入力は，それぞれ以下の形式で与えられる：

出力

答えを出力せよ．

サンプル

1
5
3 2 0 7 -12

2

$A_1, A_3, A_5$ はいずれもすでに $3$ の倍数です．
たとえば，$1$ 回目の操作で $A_2$ の値を $1$ だけ増加させ，$2$ 回目の操作で $A_7$ の値を $1$ だけ減少させることで，すべての値が $3$ の倍数になります．
また，どのように操作を行っても $2$ 回未満の操作で目標を達成することはできません．

2
4
0 0 0 0
4
0 3 6 -9

0
0