Migrated from Lutece 763 树上的鸟儿

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

作为电子科大的一员，大家都知道，我们校园有很多高大的银杏树，现在小明正在观察一棵树上的鸟儿，他发现了一些规律。

在这个树上，有一些雄鸟和雌鸟（小明很厉害，能分得出鸟儿的雄雌），假如来了一只雄鸟，它会在树上唱歌，如果$p$分钟内有一只雌鸟飞来和它一起唱，它们就会一直呆在树上不走了，否则$p$分钟之后，这只雄鸟就会飞走。假如来的是只雌鸟，如果没有落单的雄鸟在树上，它不会落到树上而是直接飞走，否则它会选择等待时间最长的雄鸟和它一起唱歌，就再也不走了。

现在小明记录了一段时间飞来这个银杏树的鸟儿，每隔一分钟可能会飞来一只雌鸟或雄鸟，或者什么都没有发生，现在小明想知道这段时间内树上最多有多少只鸟儿，你可以帮助他吗？

Input

首先输入一个正整数$T$，$T\leq 50$，表示有$T$组数据。

每组第一行给出两个整数$n$、$p$，分别表示记录时间段的长度，和每个雄鸟最多能等待的时间（$1 < n\leq 1000,1\leq p\leq 10$）。

第二行为一个长度为$n$的字符串，由 0, 1, 2三种字符构成，表示这段时间内鸟儿飞来的情况，0表示没有鸟飞来，1表示来的是雄鸟，2表示来的是雌鸟。

Output

每组数据输出一行只包含一个数，表示最多的鸟儿数量。

Samples

5
10 1
1212121212
10 3
1111122222
16 3
2221112222211111
2 1
22
5 4
11111

10
6
9
0
4

Note

如果在某个时刻，同时发生了鸟儿的飞进飞出，那么先有一只鸟儿飞出枝头，再由另一只鸟儿飞上枝头，参考第三组样例，第$15$只鸟飞上枝头的时候，第$12$只鸟已经离开了。第$12$只鸟离开的原因是因为第$15$只是雄鸟，如果第$15$只是雌鸟，第$12$只就不会飞走了。

Resources

第五届ACM趣味程序设计竞赛第三场（正式赛）