#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma comment(linker, "/stack:200000000")
 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
 
#define X first
#define Y second
 
//#include <boost/unordered_map.hpp>
//using namespace boost;
 
/*
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbtree;
rbtree T;
*/
 
using i32 = int;
using i64 = long long;
using u8 = unsigned char;
using u32 = unsigned;
using u64 = unsigned long long;
using f64 = double;
using f80 = long double;
//using i128 = __int128_t;
//using u128 = __uint128_t;
//using i128 = i64;
//using u128 = u64;
 
ll power(ll a, ll b, ll p)
{
    if (!b) return 1;
    ll t = power(a, b/2, p);
    t = t*t%p;
    if (b&1) t = t*a%p;
    return t;
}
 
ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    ll px, py;
    ll d = exgcd(b, a%b, px, py);
    x = py;
    y = px-a/b*py;
    return d;
}
 
template<class T>
inline void freshmin(T &a, const T &b)
{
    if (a > b) a = b;
}
 
template<class T>
inline void freshmax(T &a, const T &b)
{
    if (a < b) a = b;
}

template<class T>
void print(const T &a)
{
    for (auto x : a) printf("%d ", x); puts("");
}

const int MAXN = 1<<21|10;
//const i64 INF = 1000000000000000000LL;
const int INF = 1000000000;
//const int MOD = 998244353;
const int MOD = 1000000007;
const int INV2 = (MOD+1)/2;

int n;
char s[MAXN];
int u[MAXN];

int main()
{
    
    int T;
    scanf("%d", &T);
    while (T --)
    {
        scanf("%s", s+1);
        n = strlen(s+1);
        
        for (int i = 0; i <= n+1; ++ i)
            u[i] = 0;
        int cnt = 1;
        int flag = 0;
        for (int i = 1; i <= n; ++ i)
        {
            if (s[i] == '?')
            {
                cnt ++;
            }
            else
            {
                flag = 1;
                u[cnt/2] ++;
                cnt = 1;
            }
        }
        u[cnt/2] ++;
        
        if (!flag)
            printf("%d\n", n+1);
        else
        {
            int ret = 0;
            for (int i = n+1; i >= 0; -- i)
            {
                if (u[i])
                {
                    ret = i;
                    u[i] --;
                    break;
                }
            }
            
            if (ret != 0)
            {
                
                for (int i = n+1; i >= 1; -- i)
                {
                    for (int j = u[i]; j >= 1; -- j)
                    {
                        int x = i;
                        while (x)
                        {
                            int k = __lg(x);
                            if (ret>>k&1)
                            {
                                ret |= (1<<k)-1;
                                break;
                            }
                            else
                            {
                                ret |= 1<<k;
                                x ^= 1<<k;
                            }
                        }
                    }
                }
            }
            here:
            printf("%d\n", ret*2+(1-n%2));
        }
    }
    
    
    return 0;
}