Alice and Bob participate in a fishing contest! In total, they caught $$$n$$$ fishes, numbered from $$$1$$$ to $$$n$$$ (the bigger the fish, the greater its index). Some of these fishes were caught by Alice, others — by Bob.

Their performance will be evaluated as follows. First, an integer $$$m$$$ will be chosen, and all fish will be split into $$$m$$$ non-empty groups. The first group should contain several (at least one) smallest fishes, the second group — several (at least one) next smallest fishes, and so on. Each fish should belong to exactly one group, and each group should be a contiguous subsegment of fishes. Note that the groups are numbered in exactly that order; for example, the fishes from the second group cannot be smaller than the fishes from the first group, since the first group contains the smallest fishes.

Then, each fish will be assigned a value according to its group index: each fish in the first group gets value equal to $$$0$$$, each fish in the second group gets value equal to $$$1$$$, and so on. So, each fish in the $$$i$$$-th group gets value equal to $$$(i-1)$$$.

The score of each contestant is simply the total value of all fishes that contestant caught.

You want Bob's score to exceed Alice's score by at least $$$k$$$ points. What is the minimum number of groups ($$$m$$$) you have to split the fishes into? If it is impossible, you should report that.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$1 \le k \le 10^9$$$).

The second line contains a string, consisting of exactly $$$n$$$ characters. The $$$i$$$-th character is either 0 (denoting that the $$$i$$$-th fish was caught by Alice) or 1 (denoting that the $$$i$$$-th fish was caught by Bob).

Additional constraint on the input: the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print a single integer — the minimum number of groups you have to split the fishes into; or -1 if it's impossible.

Note

In the first test case of the example, you can split the fishes into groups as follows: the first three fishes form the $$$1$$$-st group, the last fish forms the $$$2$$$-nd group. Then, Bob's score will be $$$1$$$, and Alice's score will be $$$0$$$.

In the third test case of the example, you can split the fishes into groups as follows: the first fish forms the $$$1$$$-st group, the last three fishes form the $$$2$$$-nd group. Then, Bob's score will be $$$2$$$, and Alice's score will be $$$1$$$.

Competitive Fishing

Examples