在举行了一场团体比赛后,男孩 Yura 感到非常疲倦,想要改变自己的生活并搬到日本。为了纪念这一变化,尤拉将自己的名字改成了好听的名字。
被这个想法迷住了,他已经想出了一个仅由字符“_”和“^”组成的名称$$$s$$$。但有一个问题——Yura 喜欢笑脸“^_^”和“^^”。因此,名称中的任何字符都必须是至少一个此类笑脸的一部分。请注意,只有名称的连续字符才能成为笑脸。
更正式地说,考虑字符串 $$$s$$$ 中出现的所有字符串“^_^”和“^^”。那么所有这样的出现必须覆盖整个字符串 $$$s$$$,可能有交叉点。例如,在字符串“^^__^_^^__^”中,位置 $$$3,4,9,10$$$ 和 $$$11$$$ 处的字符不包含在任何表情符号内,而位置 $$$1,2,5,6,7$$$ 和 $$$8$$$ 处的其他字符包含在表情符号内。
在一次操作中,Jura 可以将字符“_”和“^”之一插入到他的名字 $$$s$$$ 中(您可以将其插入到字符串中的任何位置)。他要求你告诉他要使该名称符合 Yura 的标准所需执行的最少操作次数。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) - 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行也是唯一一行包含一个字符串 $$$s$$$ ($$$1 \leq |s| \leq 100$$$),由字符“_”和“^”组成, — 要更改的名称。
输出
对于每个测试用例,输出一个整数 - 您需要添加到名称以使其适合 Yura 的最少字符数。如果您不需要更改名称中的任何内容,请打印 $$$0$$$。
示例
输入 #1
7 ^______^ ___^_^^^_^___^ ^_ ^ ^_^^^^^_^_^^ ___^^ _
输出 #1
5 5 1 1 0 3 2
注意
在第一个测试用例中,通过添加 $$$5$$$ 字符可以获得以下名称:
^_^_^_^_^_^_^
在第三个测试用例中,我们可以在名称末尾添加一个字符“^”,然后我们得到名称:
^_^
在第四个测试用例中,我们可以在名称末尾添加一个字符“^”,然后我们得到名称:
^^
在第五个测试用例中,所有字符都已包含在笑脸中,因此答案是 $$$0$$$。
在第七个测试用例中,可以在名称开头添加一个字符“^”,在名称末尾添加一个字符“^”,则得到名称:
^_^