#include using namespace std; using ll=long long; vector S; ll N; void dfs(ll N,string R){ if(R.size()==N){ int e=0; for(int i=0;i>N>>S; for(int i=0;i0&&S.substr(i-1,2)=="00"){ an++; S[i]='1'; } if(i>1&&S.substr(i-2,3)=="010"){ an++; S[i]='1'; } } cout<>T; while(T--) solve(); }