AT_arc219_f [ARC219F] Range Division

You are given a sequence of non-negative integers $ A=(A_1,A_2,\ldots,A_N) $ of length $ N $ . You can perform the following operation on $ A $ zero or more times. In one operation, perform the following steps in order: - Choose a pair of integers $ (l,r) $ satisfying all of the following conditions: - $ 1\le l\le r\le N $ - $ A_l,A_{l+1},\ldots,A_r $ all have the same parity (that is, they are all even or all odd). - For each $ k=l,l+1,\ldots,r $ , replace $ A_k $ with $ \displaystyle\left\lfloor\frac{A_k}2 \right\rfloor $ . Find the minimum number of operations needed to make all elements of $ A $ equal to $ 0 $ . You are given $ T $ test cases; solve each of them.

The input is given from Standard Input in the following format: > $ T $ $ \text{case}_1 $ $ \text{case}_2 $ $ \vdots $ $ \text{case}_T $ Each test case is given in the following format: > $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

Output the answers for the test cases in order, separated by newlines.

### Sample Explanation 1 Consider the first test case. By performing operations as follows, all elements of $ A $ can be made $ 0 $ in five operations: - Choose $ (l,r)=(1,1) $ . $ A $ becomes $ (4,12) $ . - Choose $ (l,r)=(1,2) $ . $ A $ becomes $ (2,6) $ . - Choose $ (l,r)=(1,2) $ . $ A $ becomes $ (1,3) $ . - Choose $ (l,r)=(1,2) $ . $ A $ becomes $ (0,1) $ . - Choose $ (l,r)=(2,2) $ . $ A $ becomes $ (0,0) $ . It is impossible to make all elements of $ A $ equal to $ 0 $ in fewer than five operations, so output $ 5 $ . ### Constraints - $ 1\le T $ - $ 1\le N\le 30 $ - $ 0\le A_i< 2^{60} $ - The sum of $ N $ over all test cases is at most $ 30 $ . - All input values are integers.