幼いケビンの算数のスキルを鍛えるために、母親は次のような問題を考えました。

$n$ 個の整数 $a_1, a_2, \dots, a_n$ が与えられ、合計 $s$ は $0$ に初期化されています。ケビンは $i = 1, 2, \dots, n$ の順に以下の操作を行います。

• $a_i$ を $s$ に加える。もし結果の $s$ が偶数であれば、ケビンは $1$ 点を獲得し、その後 $s$ が奇数になるまで繰り返し $2$ で割る。

ケビンは、何回 $2$ で割ったかに関わらず、1回の操作につき最大で $1$ 点しか獲得できないことに注意してください。これらの除算はケビンの発達にとってより有益であると考えられているため、母親はケビンの合計得点が最大になるように $a$ を並べ替えたいと考えています。獲得できる得点の最大値を求めてください。

入力

各テストケースには複数のテストケースが含まれます。最初の行にはテストケースの数 $t$ ($1 \le t \le 500$) が含まれます。続いて各テストケースの説明が続きます。

各テストケースの最初の行には、整数の個数を表す単一の整数 $n$ ($1 \le n \le 100$) が含まれます。 2行目には、$n$ 個の整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) が含まれます。

出力

各テストケースについて、得点の最大値を整数で出力してください。

入出力例

入力 1

5
1
1
2
1 2
3
2 4 6
4
1000000000 999999999 999999998 999999997
10
3 1 4 1 5 9 2 6 5 3

出力 1

0
2
1
3
8

注記

最初のテストケースでは、$a$ の並べ方は $[1]$ しかありません。$s$ は $1$ になります。ケビンは得点を獲得できません。

2番目のテストケースでは、$a$ の可能な並べ方は $[2, 1]$ のみです。$s$ は順に $1$、そして $1$ になります。ケビンは両方の操作で得点を獲得します。

3番目のテストケースでは、$a$ の可能な並べ方の一つは $[2, 4, 6]$ です。$s$ は順に $1$、$5$、$11$ になります。ケビンは最初の操作で $1$ 点を獲得します。