[BJWC2018] 数字统计

小A 正在研究一些数字统计问题。有一天他突然看到了一个这样的问题： 将[L..R]中的所有整数用M 位二进制数表示（允许出现前导0）。现在将这些数中的每一个作如下变换： 从这个数的最低两位开始，如果这两位都是0，那么X=1，否则X=0。现在将这两位删去，然后将X 放在原来最低位的位置上。重复这个变换直到这个数只剩下一位为止。 例如01001 的变换过程如下： 01001-->0100-->011-->00-->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。