1388: Олівці


Відправити розв'язок


Бали:6
Time limit:1.0s
Memory limit:62M
Author:

Problem type

У Юлі є N олівців, які розташовані в ряд — назвемо таке розташування масивом із N олівців. Деякі олівці направлені доверху заточеним кінцем, деякі — донизу. Юля вважає масив гарним, якщо всі олівці направлені в одну сторону.

За одну операцію Юля може змінити напрям олівців на будь-якому послідовному відрізку олівців в масиві, тобто, після цього всі олівці, які вказували доверху, будуть вказувати донизу, і навпаки.

Знайдіть мінімальне число операцій, які прийдеться виконати Юлі, щоб масив став гарним.

Формат вхідних даних

Перший рядок вхідного потоку містить ціле число Т (1 ≤ T ≤ 3000) — кількість тестів. Наступні Т рядків містять тести — єдиний рядок S (1 ≤ |S| ≤ 50), який описує масив олівців, де і-й символ дорівнює “U”, якщо олівець направлений доверху, або “D”, якщо олівець направлений донизу.

Формат вихідних даних

Для кожного тесту в окремому рядку вивести єдине ціле число — мінімальну кількість операцій, які прийдеться виконати Юлі, щоб зробити масив гарним.

Приклад вхідних даних

1
UUDDDUUU

Приклад вихідних даних

1

Коментарі

Ще немає коментарів.