#include<stdio.h>
#include<math.h>
#include<string.h>
char s[100005];
char cs(int a){
switch(a){
case 10: return 'A';
case 11: return 'B';
case 12: return 'C';
case 13: return 'D';
case 14: return 'E';
case 15: return 'F';
default: return a+'0';
}
}
int main(){
int t,n;
while(t--){
int i,k,l,m,d;
else{
if(n==4){
k=2;
}else if(n==8) k=3;
else if(n==16) k=4;
int du=m%k;
if(du>0){
for(i=0;i<du;i++)
l=l*2+s[i]-'0';
}
l=0;
for(i=du;i<m;i++){
l=l*2+s[i]-48;
if((du > 0 && i%k==du-1)||(du==0 && i%k==k-1)){
l=0;
}}
}return 0;
}
I2luY2x1ZGU8c3RkaW8uaD4KI2luY2x1ZGU8bWF0aC5oPgojaW5jbHVkZTxzdHJpbmcuaD4KY2hhciBzWzEwMDAwNV07CmNoYXIgY3MoaW50IGEpewoJc3dpdGNoKGEpewoJCWNhc2UgMTA6IHJldHVybiAnQSc7CgkJY2FzZSAxMTogcmV0dXJuICdCJzsKCQljYXNlIDEyOiByZXR1cm4gJ0MnOwoJCWNhc2UgMTM6IHJldHVybiAnRCc7CgkJY2FzZSAxNDogcmV0dXJuICdFJzsKCQljYXNlIDE1OiByZXR1cm4gJ0YnOwoJCWRlZmF1bHQ6IHJldHVybiBhKycwJzsKCX0KfQppbnQgbWFpbigpewoJaW50IHQsbjsKCXNjYW5mKCIlZCIsJnQpOwoJd2hpbGUodC0tKXsKCQlpbnQgaSxrLGwsbSxkOwoJCXNjYW5mKCIlZCIsJm4pOwoJCXNjYW5mKCIlcyIsJnMpOwoJCWlmKG49PTIpIHByaW50ZigiJXMiLHMpOwoJCWVsc2V7CgkJbD0wO209c3RybGVuKHMpOwoJCWlmKG49PTQpewoJCQlrPTI7CgkJfWVsc2UgaWYobj09OCkgaz0zOwoJCWVsc2UgaWYobj09MTYpIGs9NDsKCQlpbnQgZHU9bSVrOwoJCWlmKGR1PjApewoJCQlmb3IoaT0wO2k8ZHU7aSsrKQoJCQlsPWwqMitzW2ldLScwJzsKCQkJcHJpbnRmKCIlYyIsY3MobCkpOwoJCX0KCQlsPTA7CgkJZm9yKGk9ZHU7aTxtO2krKyl7CgkJCWw9bCoyK3NbaV0tNDg7CgkJCWlmKChkdSA+IDAgJiYgaSVrPT1kdS0xKXx8KGR1PT0wICYmIGklaz09ay0xKSl7CgkJCQlwcmludGYoIiVjIixjcyhsKSk7CgkJCQlsPTA7CgkJCX19CgkJfXByaW50ZigiXG4iKTsKCX1yZXR1cm4gMDsKfQ==