虎哥现在开始研究字符串，如果一个由'0'和'1'组成的字符串，每个相邻字符均不相同，则被虎哥认定为合法字符串。现给定一个只含有'0','1','?'的字符串s,其中'？'可以用'0'或'1'代替,现在请你帮助虎哥编程计算一下字符串s中最多包含多少个合法的子串。

第一行为T,表示有T组测试数据
每组测试数据包含有一个由'0','1'和'?'组成的字符串s，字符串的长度在1与200000之间。

测试数据保证所有字符串的长度之和不超过200000。

每组测试数据输出一个整数，表示合法子串的个数；每组测试数据占一行。

3
0?10
???
?10??1100

8
6
25