CF1762A Divide and Conquer

An array $ b $ is good if the sum of elements of $ b $ is even. You are given an array $ a $ consisting of $ n $ positive integers. In one operation, you can select an index $ i $ and change $ a_i := \lfloor \frac{a_i}{2} \rfloor $ . $ ^\dagger $ Find the minimum number of operations (possibly $ 0 $ ) needed to make $ a $ good. It can be proven that it is always possible to make $ a $ good. $ ^\dagger $ $ \lfloor x \rfloor $ denotes the floor function — the largest integer less than or equal to $ x $ . For example, $ \lfloor 2.7 \rfloor = 2 $ , $ \lfloor \pi \rfloor = 3 $ and $ \lfloor 5 \rfloor =5 $ .

Each test contains multiple test cases. The first line contains a single integer $ t $ ( $ 1 \leq t \leq 1000 $ ) — the number of test cases. The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1 \leq n \leq 50 $ ) — the length of the array $ a $ . The second line of each test case contains $ n $ space-separated integers $ a_1,a_2,\ldots,a_n $ ( $ 1 \leq a_i \leq 10^6 $ ) — representing the array $ a $ . Do note that the sum of $ n $ over all test cases is not bounded.

For each test case, output the minimum number of operations needed to make $ a $ good.

In the first test case, array $ a $ is already good. In the second test case, we can perform on index $ 2 $ twice. After the first operation, array $ a $ becomes $ [7,2] $ . After performing on index $ 2 $ again, $ a $ becomes $ [7,1] $ , which is good. It can be proved that it is not possible to make $ a $ good in less number of operations. In the third test case, $ a $ becomes $ [0,2,4] $ if we perform the operation on index $ 1 $ once. As $ [0,2,4] $ is good, answer is $ 1 $ . In the fourth test case, we need to perform the operation on index $ 1 $ four times. After all operations, $ a $ becomes $ [0] $ . It can be proved that it is not possible to make $ a $ good in less number of operations.