xjj买了一幅昂贵的新画，决定把它展示给他的n朋友们看。他把画挂在自己的房间里。他的n个朋友一个接一个地进进出出。换句话说，第一个朋友先进后出，然后是第二个，依此类推。

在开始时(拜访朋友之前)，房间里挂着一幅画。最后(在n个朋友之后)，这幅画消失了。具体是什么时候消失的--没有任何信息。于是xjj一个一个地问他的朋友们。当他进房间时，是否有一幅画。每个朋友都回答了三个答案中的其中一个：

没有(回答0)

有(回答1)

不记得了(回答？)。

除小偷外，其他人要么不记得，要么说的都是事实。小偷可以说任何事情(三个选项中的任何一个)。xjj不知道小偷是谁。他让你根据被询问者的朋友的回答找出所有可以被认为成是小偷的人数。

第一个数字t( 1≤t≤10^4)测试中的测试用例数。

下面是测试用例的说明。

每个测试用例的第一行包含一个字符串s(长度不超过10⁵ )--对朋友答案的描述，其中表示第i个朋友的答案。字符串中的每个字符要么是 0，要么是 1，要么是?给定的规律性是在实际情况中描述的。特别是，根据答案，至少可以怀疑一位朋友偷了一幅画。