小 A 正在研究一些数字统计问题。有一天他突然看到了一个这样的问题：
将 中的所有整数用 位二进制数表示（允许出现前导 ）。现在将这些数中的每一个作如下变换：
从这个数的最低两位开始，如果这两位都是 ，那么 ，否则 。现在将这两位删去，然后将 放在原来最低位的位置上。重复这个变换直到这个数只剩下一位为止。
例如 的变换过程如下：
现在的问题是变换后的所有数中，值为 （ 为 或 ）的有多少个？
小 A 不会了，他想让你帮助他完成这个问题。
输入文件包含多组测试数据。
第一行，一个整数 ，表示测试数据的组数。
接下来的 节，每节对应一组测试数据，格式如下：
第一行，两个整数 。
第二行，两个 位二进制数 。
对于每组测试数据，输出一行，一个二进制数，表示该组测试数据中 中的所有整数变换后的值为 的个数。这里的二进制数不允许出现前导 。
1 3 1 001 101
11
对于 的数据，，。
