题目描述

小 A 正在研究一些数字统计问题。有一天他突然看到了一个这样的问题：

将 $[L..R]$ 中的所有整数用 $M$ 位二进制数表示（允许出现前导 $0$）。现在将这些数中的每一个作如下变换：

从这个数的最低两位开始，如果这两位都是 $0$，那么 $X=1$，否则 $X=0$。现在将这两位删去，然后将 $X$ 放在原来最低位的位置上。重复这个变换直到这个数只剩下一位为止。

例如 $01001$ 的变换过程如下：$01001 \to 0100 \to 011 \to 00 \to 1$。

现在的问题是变换后的所有数中，值为 $Y$（$Y$ 为 $0$ 或 $1$）的有多少个？

小 A 不会了，他想让你帮助他完成这个问题。

输入格式

输入文件包含多组测试数据。

第一行，一个整数 $T$，表示测试数据的组数。

接下来的 $T$ 节，每节对应一组测试数据，格式如下：

第一行，两个整数 $M$、$Y$。

第二行，两个 $M$ 位二进制数 $L$、$R$。

输出格式

对于每组测试数据，输出一行，一个二进制数，表示该组测试数据中 $[L..R]$ 中的所有整数变换后的值为 $Y$ 的个数。这里的二进制数不允许出现前导 $0$。

1
3 1
001 101

11

提示

对于 $20\%$ 的数据：$1 ≤ M ≤ 16$。

对于 $40\%$ 的数据：$1 ≤ M ≤ 32$。

对于 $100\%$ 的数据：$1 ≤ M ≤ 200，1 ≤ T ≤ 50$。