该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

问题描述

给定一个长度为 $n$ 的序列 $A$，你每次可以做如下操作：

• 选择两个不同的下标 $i$, $j$，令 $A_{i} = A_{i} \times A_{j}$ 。

请问最少操作多少次，可以使得序列中恰好有 $m$ 个正数，如果无法做到请你输出 $-1$。

输入格式

本题有多组测试数据

第一行一个正整数 $t$，表示测试数据组数 （$1 \le t \le 10^5$)

对于每组测试数据：

第一行输入两个整数 $n, m (1 \leq n \leq 10^{5}, 0 \leq m \leq n)$

第二行输入 n 个整数 $A_{i}(-10^{9} \leq A_{i} \leq 10^{9})$

保证 $\sum n \leq 10^{5}$

输出格式

对于每组测试数据，输出最少操作多次可以使得序列中恰好有 $m$ 个正数，如果无法做到请你输出 $-1$

样例

2
4 2
2 4 3 -1
4 4
-1 -3 -4 -5

1
-1

样例解释1

• 对于第一组测试数据，可以选择 $i = 3$，$j = 4$，令 $A_{3} = A_{3} \times A_{4} = 3 \times (-1) = -3$ ，此时序列中正数个数变为 $2$ 个，故最少操作 $1$ 次。

• 对于第二组测试数据，初始所有数都为负数，通过操作至多变成 $3$ 个正数，无法达到 $4$ 个，输出 $-1$。