幼儿园有N个小朋友，有男孩也有女孩，他们按照水平方向拍成一行，每个小朋友所占的位置编号分别是1，2，....,N。

你是幼儿园的老师，幼儿园有两种糖果，分别是男孩喜欢的糖果和女孩喜欢的糖果。现在有一定数量的篮子，每个篮子只能装一种糖果，装糖果的数量可以是无限的。由于小朋友比较小，至多愿意移动k个位置到装有自己喜欢的糖果的篮子里去取糖。现在需要你选择1，2,.....,N的位置放置糖果篮，每个位置只能放一个糖果篮。由于篮子的数量有限，现在请你计算出最少需要多少个篮子能保证每个小朋友都能取到自己喜欢的糖果。

每个测试用例包含 T个子测试用例，每个子测试用例描述一种小朋友的排列。

输入的第一行包含 整数T。以下是 T 个子测试用例。

每个子测试用例的第一行包含两个整数N和K(1<=N<=2*10^5,0<=K<=N-1)，第二行为一行由N个0或1组成的字符串。0表示男孩，1表示女孩。从左往右第i个字符表示第i个位置是男孩还是女孩。

一共有T行，每行一个整数，表示每个测试用例需要的最少的篮子数量

1<=T<=10

1<=N<=2*10^5

0<=K<=N-1