度度熊与运算式 1

Accepts: 552
Submissions: 2532
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)
Problem Description
某天度熊发现了一个由 $n+1$ 个数字 $1$ 组成的运算式如下: 1 $op_1$ 1 $op_2$ 1 $\ldots$ 1 $op_n$ 1 其中 $op_i$ 可能是 $\oplus$ (按位异或运算) 或是 $?$ (问号)。 例如当 $n=5$ 时,式子可能长成这样:$1\oplus1\ ?\ 1\oplus1\ ?\ 1\ ?\ 1$ 现在,度熊想把所有的 `?` 取代为 $+$ 或 $\oplus$。 (贴心提示: 加法运算的优先级比按位异或运算还高) 请问取代完后此运算式可能的最大运算结果为何?
Input
有多组询问,第一行包含一个正整数 $T$ 代表有几组询问,接着每组测试数据占一行,包含一个长度为 $n$ 的字符串,仅由 `^` 和 `?` 组成,第 $i$ 个字符若是 `^' 就代表 $op_i=\oplus$,否则 $op_i$ 就是问号。($n$ 的值不会在数据中出现,请由字符串长度来判断。) * $1 \le n \le 2^{21}-2$ * 所有询问的 $n$ 的总和不超过 $2 \times 10^7$
Output
对于每一个询问输出一行包含一个整数代表答案,也就是该算式的问号被取代后可能的最大运算结果。
Sample Input
4
?
??
^^
^^^
Sample Output
2
3
1
0

Note
样例的第一组询问算式为:`1?1`。取代后有 $2$ 种可能 $1+1$ 和 $1\oplus1$,其中 $1+1=2$、$1\oplus1=0$,所以最大的可能值是 $2$。

样例的第二组询问算式为:`1?1?1`。取代后有 $4$ 种可能 $1+1+1$,$1+1\oplus1$,$1\oplus1+1$ 和 $1\oplus1\oplus1$,其中 $1+1+1=1+1\oplus1=1\oplus1+1=3$、$1\oplus1\oplus1=1$,所以最大的可能值是 $3$。

样例的第三组询问算式为:$1\oplus1\oplus1$。并不包含问号,只有唯一的运算结果 $1$。

样例的第四组询问算式为:$1\oplus1\oplus1\oplus1$。并不包含问号,只有唯一的运算结果 $0$。