AT_arc219_f [ARC219F] Range Division

長さ $ N $ の非負整数列 $ A=(A_1,A_2,\ldots,A_N) $ が与えられます。 $ A $ に対して操作を $ 0 $ 回以上行うことができます。 $ 1 $ 回の操作では、以下の手順を順に行います： - 以下の条件を全て満たす整数の組 $ (l,r) $ を選ぶ。 - $ 1\le l\le r\le N $ - $ A_l,A_{l+1},\ldots,A_r $ の偶奇が全て同じである - $ k=l,l+1,\ldots,r $ に対し、 $ A_k $ を $ \displaystyle\left\lfloor\frac{A_k}2 \right\rfloor $ で置き換える。 $ A $ の要素を全て $ 0 $ にするために必要な操作回数の最小値を求めてください。 $ T $ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

各テストケースに対する答えを順に改行区切りで出力せよ。

### Sample Explanation 1 $ 1 $ 番目のテストケースについて考えます。 以下のように操作することで $ 5 $ 回で $ A $ の要素を全て $ 0 $ にすることができます： - $ (l,r)=(1,1) $ を選ぶ。 $ A=(4,12) $ となる。 - $ (l,r)=(1,2) $ を選ぶ。 $ A=(2,6) $ となる。 - $ (l,r)=(1,2) $ を選ぶ。 $ A=(1,3) $ となる。 - $ (l,r)=(1,2) $ を選ぶ。 $ A=(0,1) $ となる。 - $ (l,r)=(2,2) $ を選ぶ。 $ A=(0,0) $ となる。 $ 5 $ 回未満の操作で $ A $ の要素を全て $ 0 $ にすることはできないので、 $ 5 $ を出力してください。 ### Constraints - $ 1\le T $ - $ 1\le N\le 30 $ - $ 0\le A_i< 2^{60} $ - 全てのテストケースにおける $ N $ の総和は $ 30 $ 以下 - 入力される値は全て整数