题目描述

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

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

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

例如 $01001$ 的变换过程如下：

$01001 \rightarrow 0100 \rightarrow 011 \rightarrow 00 \rightarrow 1$

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

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

输入格式

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

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

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

第一行，两个整数 $m,y$。

第二行，两个 $m$ 位二进制数 $L,R$。

输出格式

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

1
3 1
001 101

11

数据规模与约定

对于 $100\%$ 的数据，$1 \le m \le 200$，$1 \le T \le 50$。