题目

After holding one team contest, boy Yura got very tired and wanted to change his life and move to Japan. In honor of such a change, Yura changed his name to something nice.

Fascinated by this idea he already thought up a name s consisting only of characters ““ and “^”. But there’s a problem — Yura likes smiley faces “^^” and “^^”. Therefore any character of the name must be a part of at least one such smiley. Note that only the consecutive characters of the name can be a smiley face.

More formally, consider all occurrences of the strings “^^” and “^^” in the string s. Then all such occurrences must cover the whole string s, possibly with intersections. For example, in the string “^^__^^^__^” the characters at positions 3,4,9,10 and 11 are not contained inside any smileys, and the other characters at positions 1,2,5,6,7 and 8 are contained inside smileys.

In one operation Jura can insert one of the characters “_” and “^” into his name s (you can insert it at any position in the string). He asks you to tell him the minimum number of operations you need to do to make the name fit Yura’s criteria.

Input

Each test consists of multiple test cases. The first line contains a single integer t(1≤t≤100) —the number of test cases. The description of test cases follows.

The first and only line of each test case contains a single string s (1≤|s|≤100), consisting of characters “_” and “^”, — the name to change.

Output

For each test case, output a single integer — the minimum number of characters you need to add to the name to make it fit for Yura. If you don’t need to change anything in the name, print 0.

Example

第一次做英文编程题，看得有点懵，大概是在说，输入多行字符串，每个字符串由^或下划线组成，要求每个字符串的每个字符都能和相邻的字符组成^^或^_^，问需要添加的 ^ 和下划线的最小数目是多少

我的思路是，遍历字符串，搜索下划线，找到就观察其相邻两边是否有 ^ ，两边都有就直接删除掉这个下划线；只有一个就计数加一，并删除这个下划线；一个都没有就计数加二，删除该下划线并在该位置插入一个 ^；只有一个字符的字符串单独处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include  <iostream>
#include <string>
using namespace std;

int  main()
{
	string str;
	int n, pos, res[100] = { 0 };
	cin >> n;
	getline(cin, str);	// 把前面cin遗留的结束符处理掉

	for (int i = 0; i < n; i++)
	{
		getline(cin, str);

		if (str == "^")
			res[i]++;
		while ((pos = str.find('_')) != string::npos)	// 字符串中没有'_'时停止
		{
			if (0 == pos)	// '_'在第一个位置
			{
				if ('^' == str[pos + 1])
				{
					res[i]++;
					str.erase(pos, 1);	// 删除'_'
					break;
				}
				else
				{
					str.erase(pos, 1);	// 删除'_'
					str.insert(pos, 1, '^');
					res[i] += 2;
				}
			}
			else if (str.size() - 1 == pos)	// '_'在最后一个位置
			{
				if ('^' == str[pos - 1])
				{
					res[i]++;
					str.erase(pos, 1);	// 删除'_'
					break;
				}
				else
				{
					str.erase(pos, 1);	// 删除'_'
					str.insert(pos, 1, '^');
					res[i] += 2;
				}
			}
			else	// '_'在中间
			{
				if ('^' == str[pos - 1])
				{
					if ('^' == str[pos + 1])
					{
						str.erase(pos, 1);
					}
					else
					{
						res[i]++;
						str.erase(pos, 1);
					}
				}
				else if ('^' != str[pos - 1])
				{
					if ('^' == str[pos + 1])
					{
						str.erase(pos, 1);
						res[i]++;
					}
					else
					{
						res[i] += 2;
						str.erase(pos, 1);
						str.insert(pos, 1, '^');
					}
				}
			}
		}
	}

	for (int i = 0; i < n; i++)
		cout << res[i] << endl;

	return 0;
}

如果有更好的写法欢迎在评论区给出噢^_^