Migrated from Lutece 2535 土豆的炼丹术

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

土豆有世界上最强的炼丹术。一天，土豆在机缘巧合之下获得了 $T$ 个二进制数字，他决定把这 $T$ 个二进制数字炼成丹药。

炼丹炉可以把一个二进制数字转换成十进制，得到的十进制数字就是炼成的丹药，而丹药的价值为这个十进制数字各个数位之和。

土豆现在决定对这 $T$ 个二进制数字单独处理。为了使每个二进制数字物尽其用，土豆决定用一把神奇的剪刀将一个二进制数字剪开，得到多个二进制数字。比如，他可以将 $10001$ 剪开变成 $1000,1$。然而，这把神奇的剪刀法力有限，且恢复速度不快，在对一个二进制数字进行操作时，它只恢复了部分的法力，最多只能使用 $m$ 次。

将一个二进制数字剪开后，土豆将得到的新的二进制数字分别投入炼丹炉中，得到多个丹药，每个丹药的价值单独计算，由该数字炼成的所有丹药价值之和是丹药总价值。

请问这 $T$ 个二进制数字土豆能获得的最大丹药总价值分别是多少。

Input

第一行一个正整数 $T$。

接下来给出 $T$ 组数据，每组数据两行。

第一行两个整数 $n,m$，分别表示二进制数字的位数和剪刀可以使用的次数。

第二行一个 $n$ 位的二进制数字（可能包含前缀 $0$）。

Output

对于每组数据，输出一行一个整数，表示最大丹药总价值。

Samples

1
5 2
10001

9

Constraints

$1\le T\le 800$

$1\le n\le 800$

$T\le \sum n\le 800$

$0\le k\le 800$

Note

对于样例，土豆可以这样炼丹：

土豆可以使用一次剪刀将 $10001$ 剪成 $1000,1$ 两个二进制数字，炼丹后丹药分别为 $8$ 和 $1$，价值分别为 $8$ 和 $1$，总价值 $8+1=9$。

如果土豆不使用剪刀，得到的丹药为 $17$，价值为 $1+7=8$，总价值为 $8$。

土豆也可以使用两次剪刀，但是无法得到价值大于 $9$ 的丹药。

Resources

2021 UESTC ICPC Training for Dynamic Programming