U378506 小明的新名字

小明更把自己的名字改成了一个字符串s，它只包含字符```_```和```^```。小明喜欢笑脸“^_^”和“^^”。因此，名字中的每个字符必须至少是其中一个笑脸的一部分。请注意，名字中仅连续的字符可以成为笑脸。可能存在交集。例如，在字符串“^^__^^^__^”中，位置 3、4、9、10 和 11 的字符不包含在任何笑脸内，而在位置 1、2、5、6、7 和 8 的字符包含在笑脸内。在一次操作中，小明可以向他的名字 s 中插入字符“_”和“^”中的一个（可以在字符串的任何位置插入）。请你告诉他最少需要进行多少次操作才能使字符合小明的标准。

每个测试由多个测试用例组成。第一行包含单个整数t(1≤t≤100),t为测试用例的数量。每个测试用例的第一行（也是唯一的一行）包含一个待修改的字符串s(1≤|S|≤100），由字符 “_” 和 “^” 组成。

对于每个测试用例，输出一个整数——你需要添加到名字中的最少字符数，使其适合小明的要求。如果不需要更改名字，则输出0。

#### 时间限制：1s #### 空间限制：128MB