#include <bits/stdc++.h>

using namespace std;

int cnt[2500000],num[30];
char str[2500000];

int main() {
  int cases;
  scanf("%d",&cases);
  for(;cases;cases--) {
      scanf("%s",str+1);
      int n=strlen(str+1)+1;
      for(int i=1;i<=n;i++) cnt[i]=0;
      int s=0;
      for(int i=1;i<=n;i++) {
          s++;
          if (str[i]!='?') {
              cnt[s]++;
              s=0;
          }
      }
    int tot=0;
    for(int i=n;i>0&&tot<20;i--) {
        while (cnt[i]&&tot<20) {
            cnt[i]--;
            num[++tot]=i;
        }
    }
    int ans=0;
    for(int i=20;i>0;i--) {
        int id=0;
        for(int j=1;j<=tot;j++)
          if (num[j]>num[id]) id=j;
        if (num[id]>=(1<<i)) {
            ans+=(1<<i);
            num[id]-=(1<<i);
        }
    }
    ans+=(n&1);
    printf("%d\n",ans);
  }
  return 0;
}