Description

$Monkey$发掘出了一个长度为$n$的仅有$0$和$1$组成的序列$a$。

现在，$Monkey$定义$x$翻转操作：将该序列中一段连续的且长度为$x$的区间中的每位元素进行翻转（当某一位进行翻转操作时，若当前位为$0$，进行翻转操作后其值变为$1$；若当前位为$1$，进行翻转操作后其值变为$0$）。

$Monkey$想知道将整个数组的每一位数都变为$1$的最小操作次数，若不能将完成则输出$-1$。

Input Format

第一行输入一个正整数$T$（$1≤T≤10000$），表示共有$T$组测试样例。

对于每组测试样例：

第一行输入两个整数$n$（$1≤n≤10^5$），$x$（$1\le x\le n$），其中$n$表示序列$a$的长度，$x$为$x$翻转操作的$x$ 。

第二行输入一个仅由$0$和$1$组成的长度为$n$的序列，表示序列$a$。

题目保证所有测试样例$n$的总和不超过$10^5$。

Output Format

对于每组测试样例，输出一行，包含一个正整数，表示答案。

1
8 3
0 0 0 1 0 1 1 0

3

Source

1816 Online Judge 10.100.0.232