Flower 准备用一排气球来装饰房间。他有 个气球排成一行，气球的颜色有三种，分别为红色（使用字母 表示）、黄色（）和白色（）。不同颜色的气球能带来不同的愉悦度：红色为 ，黄色为 ，白色为 。 为了达到最好的装饰效果，Flower 决定从中选取一个非空的连续子区间。选定区间后，他会邀请 Rainbow 对该区间施展一次魔法。Rainbow 的魔法包含以下两个步骤： 第一步，「颜色反转」：选择是否将区间内所有红色气球全变成黄色、黄色气球全变成红色（同时进行）。 第二步，「点缀」：他可以将区间内至多 个白色气球染成红色。 Flower 希望经过 Rainbow 的魔法处理后，该区间的气球愉悦度之和至少为 。 为了节省空间，Flower 希望他选取的这个区间长度尽可能短。请你帮助他判断这样的区间是否存在，如果存在，计算满足条件的最小区间长度。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数，每组测试数据描述如下：第一行输入三个整数 ，表示气球数量、「点缀」最多可处理的气球数量、期望的愉悦度之和；第二行输入一个长度为 、仅由字符 , , 组成的字符串 ，表示每个气球的颜色。除此之外，保证单个测试文件的 之和不超过 。

输出描述:

对于每一组测试数据，新起一行。若存在合法的区间，输出最小区间长度；否则输出 。