22128번 - Молекула 다국어

В результате последних исследований в сверхсекретной лаборатории было открыто новое вещество. Каждая молекула этого вещества представляет цикл, состоящий из двух видов атомов, которые мы будем условно называть черными и белыми (настоящие названия атомов держатся в строгом секрете). Для проведения сверхсекретной реакции необходимо перевести молекулу в нестабильное состояние, в котором она может распасться на две независимые молекулы, каждая из которых состоит только из одного вида атомов.

Исследования показали, что молекула распадается, если все атомы каждого цвета образуют непрерывный блок.

Для перестроения молекулы ученые могут осуществлять следующую операцию: непрерывная последовательность атомов вырезается из цикла и вставляется в другое место. Пример перестроения молекулы приведен на рисунке.

Теперь ученые пытаются выяснить, за какое минимальное число описанных операций можно привести молекулу в нестабильное состояние. Помогите им это выяснить.

В первой строке входного файла содержится натуральное число n — число молекул, которые необходимо исследовать.

В каждой из следующих n строк содержится описание одной молекулы в следующем формате: строка, состоящая не менее чем из трех букв w и b, обозначающих белый и черный атомы, соответственно. Гарантируется, что каждая буква встречается в каждой молекуле хотя бы один раз. Суммарная длина всех молекул не превышает 200000.

Выведите n строк. В i-ой строке выведите минимальное число операций, которое необходимо выполнить, чтобы i-я молекула перешла в нестабильное состояние.