AT_pakencamp_2025_day3_h OR Preference

**メモリ制限が特殊であることに注意してください。** $ T $ 個のテストケースについて以下の問題を解いてください。 長さ $ N $ の整数列 $ A = (A_0, A_1, \dots, A_{N-1}) $ が与えられます。 あなたは、配列の長さが 1 になるまで、次のいずれかの操作を繰り返し行います。 - $ \mathrm{AND} $ 操作：隣り合う 2 要素 $ (a, b) $ を選び、これらをマージして 1 つの要素に置き換える。このとき、新しい要素は $ a \,\&\, b $ とする。 - $ \mathrm{OR} $ 操作：隣り合う 2 要素 $ (a, b) $ を選び、これらをマージして 1 つの要素に置き換える。このとき、新しい要素は $ a \,|\, b $ とする。 最終的に配列の要素が 1 つになったとき、その値が $ 0 $ でなければなりません。 この条件を満たすような操作列のうち、「 $ \mathrm{OR} $ 操作」を行う回数の最大値を求めてください。 ただし、そのような操作列が存在しない場合は $ -1 $ を出力してください。

入力は以下の形式で標準入力から与えられる。入力の $ 1 $ 行目は以下の形式である。 > $ T $ その後、 $ T $ 個のテストケースが続く。各テストケースは以下の形式で与えられる。 > $ N $ $ A_{1} $ $ A_{2} $ $ \cdots $ $ A_{N} $

$ T $ 行出力せよ。 $ i $ 行目には、 $ i $ 番目のテストケースにて行うことができる $ \mathrm{OR} $ 操作の回数の最大値を求めよ。

### 部分点 この問題では、次の規則で提出に対する得点が定められる。 - 全ての入力ケースで AC を得た場合、満点が得られる。 - そうでなかった場合、 $ m = 1,2 \ldots 12 $ について次の規則で部分点を得ることができる。 - 「各テストケースにおける $ N $ の総和が $ 2^m $ を超えないかつ、 $ A_i < 2^m $ 」という条件を満たす全ての入力ケースで AC を得た場合、追加で $ m $ 点を得ることができる。 - 例えば、「各テストケースにおける $ N $ の総和が $ 2^4 (=16) $ を超えないかつ、 $ A_i < 2^4 $ 」という条件を満たす全ての入力ケースで AC を得た場合、 $ 1+2+3+4 $ 点、すなわち $ 10 $ 点を得ることができる。 ### Sample Explanation 1 この入力には、 $ 4 $ つのテストケースが含まれます。 $ 1 $ つ目のテストケースについて、次のような手順で $ 2 $ 番目の操作を $ 3 $ 回行うことができます。 - 最初、 $ A = (3,0,1,4,1,5) $ である。 - $ (A_{3}, A_{4}) $ に対して $ \mathrm{OR} $ 操作を行う。操作後、 $ A = (3,0,5,1,5) $ となる。 - $ (A_{1}, A_{2}) $ に対して $ \mathrm{AND} $ 操作を行う。操作後、 $ A = (0,5,1,5) $ となる。 - $ (A_{3}, A_{4}) $ に対して $ \mathrm{OR} $ 操作を行う。操作後、 $ A = (0,5,5) $ となる。 - $ (A_{2}, A_{3}) $ に対して $ \mathrm{OR} $ 操作を行う。操作後、 $ A = (0,5) $ となる。 - $ (A_{1}, A_{2}) $ に対して $ \mathrm{AND} $ 操作を行う。操作後、 $ A = (0) $ となる。 この操作方法は、最終的に $ A_{1} = 0 $ が成立しているため条件を満たします。 $ \mathrm{OR} $ 操作を $ 4 $ 回以上行う方法であって、条件を満たすように操作を行うことはできないため答えは $ 3 $ となります。 ### Constraints - $ 1 \leq T \leq 2^{12} $ - $ 2 \leq N \leq 2^{13} $ - $ 0 \leq A_{i} < 2^{13} $ - 各テストケースにおける $ N $ の総和は $ 2^{13} $ を超えない - 入力は全て整数