#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
char a[5000005];
vector<int>v;
int vis[25];
int main()
{
  int t;
  scanf("%d",&t);
  while(t--){
    scanf("%s",a);
    v.clear();
    for(int i=0;i<=21;i++) vis[i]=0;
    int len=strlen(a);
    int cnt=1;
    for(int i=0;i<len;i++){
      if(a[i]=='?') cnt++;
      else {
        v.push_back(cnt);
        cnt=1;
      }
    }
    v.push_back(cnt);
    ll ans=0,tmp=0;
    for(int i=0;i<v.size();i++){
      tmp+=v[i];
      tmp%=2;
      int tmpp=v[i];
      for(int j=21;j>=1;j--){
        if(tmpp>=(1<<j)&&vis[j]==0){
          vis[j]=1;
          tmpp-=(1<<j);
          ans+=(1<<j);
        }
      }
    }
    ans+=tmp;
    printf("%I64d\n",ans);
  }
  return 0;
}