분자

최근 초비밀 연구소의 연구 끝에 새로운 물질이 발견되었다. 이 물질의 각 분자는 검은색과 흰색이라고 부르는 두 종류의 원자로 이루어진 고리이다(원자의 실제 이름은 극비에 부쳐져 있다). 초비밀 반응을 진행하려면 분자를 불안정한 상태로 만들어야 하는데, 이 상태에서는 분자가 한 종류의 원자로만 이루어진 두 개의 독립된 분자로 분해될 수 있다.

연구 결과, 각 색의 원자가 모두 연속된 한 덩어리를 이루면 분자가 분해된다는 사실이 밝혀졌다.

분자를 재배열하기 위해 과학자들은 다음과 같은 연산을 할 수 있다. 고리에서 연속된 원자 열을 잘라 내어 다른 위치에 삽입한다. 분자를 재배열한 예가 그림에 나와 있다.

이제 과학자들은 분자를 불안정한 상태로 만들기 위해 필요한 최소 연산 횟수를 알아내려고 한다. 그들을 도와 이 값을 구하자.

첫째 줄에 조사할 분자의 수 $n$이 주어진다.

다음 $n$개 줄에는 각 분자의 설명이 주어진다. 각 줄은 흰색과 검은색 원자를 나타내는 문자 w와 b로만 이루어진 길이 3 이상의 문자열이다. 각 문자가 각 분자에 적어도 한 번씩은 나타난다고 보장된다. 모든 분자의 길이 합은 200000을 넘지 않는다.

$n$개 줄을 출력한다. $i$번째 줄에는 $i$번째 분자를 불안정한 상태로 만들기 위해 필요한 최소 연산 횟수를 출력한다.