小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。

【数据范围】 

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

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

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