CF1744D Divisibility by 2^n

你被给予一个正整数数列 $ a_1, a_2, \ldots, a_n $ . 你需要让数列中所有数字的乘积 (也就是 $ a_1 \cdot a_2 \cdot \ldots \cdot a_n $ ) 能被 $ 2^n $ 整除. 你可以进行下列操作任意次: - 选择一个正整数 $ i $ ( $ 1 \leq i \leq n $ ) 然后把 $ a_i $ 替换为 $ a_i=a_i \cdot i $ . 你不能重复地对同一个 $ i $ 进行操作. 换句话说, 你选择的所有的 $ i $ 都必须不同. 你要找到让数列中所有数字的乘积能被 $ 2^n $ 整除的最少操作. 注意方案不一定存在.

**本题有多组数据.** 输入的第一行只包含一个正整数 $ t $ $ (1 \leq t \leq 10^4 )$ — 测试数据的数目. 接下来 $ 2 \cdot t $ 行, 是 $ t $ 组数据. 每组数据的第一行只包含一个正整数 $ n $ ( $ 1 \leq n \leq 2 \cdot 10^5 $ ) — 数列的长度 $ a $ . 每组数据的第二行包含 $ n $ 个正整数: $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_i \leq 10^9 $ ). 保证所有测试数据中 $ n $ 的和不超过 $ 2 \cdot 10^5 $ .

对每组数据, 输出让数列中所有数字的乘积能被 $ 2^n $ 整除的最少操作. 如果方案不存在，请输出$-1$.

在第一个测试数据中, 数列中所有数字的乘积已经为 $ 2 $ , 因此不需要操作. 在第二个测试数据中, 数列中所有数字的乘积为 $ 6 $ . 我们可以对 $ i = 2 $ 进行操作, 于是 $ a_2 $ 变为 $ 2\cdot2=4 $ , 然后数列中所有数字的乘积为 $ 3\cdot4=12 $ , 这个数字能被 $ 2^n=2^2=4 $ 整除. 在第四个测试数据中, 就算我们执行所有可能的操作, 我们还是无法让数列中所有数字的乘积能被 $ 2^n $ 整除 — 结果为 $ (13\cdot1)\cdot(17\cdot2)\cdot(1\cdot3)\cdot(1\cdot4)=5304 $ , 不能被 $ 2^n=2^4=16 $ 整除. 在第五个测试数据中, 我们可以对 $ i = 2 $ 和 $ i = 4 $ 进行操作.