题目描述

有一个男人叫小帅，他喜欢小美。在他第$100$次向小美表白时，小美给他提出一个问题，若他答对就同意和他在一起。
问题如下 ：
给定一个长度为 $n$ 的序列 $a$，你每次可以做如下操作：

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

请问最少操作多少次，可以使得序列中恰好有 $m$ 个正数，如果无法做到请你输出 $-1$。
小帅真的很喜欢小美，所以请你一定要帮帮他呜呜呜。

输入格式

本题有多组测试数据

第一行输入一个整数 $T(1 \leq T \leq 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

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

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