Description

有n盏灯，每盏灯熄灭表示0，亮着表示1，灯的状态可以表示一个n位二进制数，其中最左边的是最高位，最右边的是最低位。

你开始观察这些灯，你知道每+1s钟时间，这些灯会修改自己的状态，使得它们所代表的二进制数增加1。当灯表示的是2^n-1时（所有灯都亮着），下1s钟这些灯就会全部熄灭，表示的数字变为0，然后继续+1s+1s……

然而，可能有些灯是坏的（也可能没有坏灯），坏的灯永远都亮不起来，即使它们对应了数字1时也不会亮。你不知道哪些灯坏了。

现在是第0秒，你能看到每盏灯是亮还是灭，你也知道此时恰好有k盏灯应该是亮的（即所代表的二进制数恰好有k位，虽然其中可能有些灯因为坏了而没亮）。保证k不小于当前亮着的灯数量。

假设你继续观察这些灯的变化，你需要再等多少秒才保证能够确定当前灯所表示的二进制数是多少？（只需要确定二进制数是多少，不需要确定哪些灯是坏的）你有可能在第0秒就确定了当前的二进制数，也有可能你永远也确定不了。

Format

Input

第一行一个整数t，表示询问数量。

接下来每组询问的第一行包含n和k，接下来一行包含n个0或1的数字，从左到右表示灯的亮灭状态。

Output

对于每个询问输出一行，表示至少需要再等多少秒才可以保证确定当前的二进制数。输出-1表示永远无法确定。

Samples

5
3 2
1 0 0
3 2
0 0 1
7 4
0 1 0 0 1 0 0
20 15
1 1 0 0 0 0 1 0 1 1 0 0 0 1 1 1 1 0 0 1
20 19
0 1 1 0 1 0 0 0 1 1 0 0 0 1 1 0 1 0 1 0

2
-1
19
217601
8193

Hint

样例解释： 第一个询问中，第0秒时的二进制数只能是101(5)或110(6)，下一秒钟只能是110(6)或111(7).

但如果右边两盏灯都是坏的，你仍然会无法决定，需要再等1秒钟，只能是111(7)或000(0)，这时你可以通过左边这盏灯的亮灭来判断是7还是0

对于10%的数据n<=3。

对于30%的数据n<=10。

对于50%的数据n<=20。

对于100%的数据n<=60。

对于100%的数据，0<=k<=n,t<=300。