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

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

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

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

Перший рядок вхідного потоку містить ціле число ~Т~ ~(1 ≤ T ≤ 3000)~ — кількість тестів.

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

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

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

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

1
UUDDDUUU

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

1