Minimum Insertions to Create a Harmonious String

You are given a string s. You can perform an insertion operation by inserting any character at any position in the string (including the beginning or the end). A string is defined to be harmonious if it contains at least one pair of adjacent identical characters. Your task is to compute the minimum number of insertions required to make the string harmonious.

Details:

• If the length of s is less than 2, then one insertion is required because the minimum length to have an adjacent pair is 2.
• If s already contains two identical adjacent characters, it is already harmonious and no insertion is needed.
• If none of the above conditions hold, you will need exactly 2 insertions to create at least one adjacent pair.

You need to process multiple test cases.

inputFormat

The input is given via stdin and has the following format:

T
s1
s2
...
sT

Here, T is the number of test cases, and each of the following T lines contains a string s.

outputFormat

For each test case, output a single integer on its own line representing the minimum number of insertions required to make the string harmonious. The output should be printed to stdout.

## sample

3
abc
a
aabb

2
1
0

</p>