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

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

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

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

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

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

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

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

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

1
UUDDDUUU

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

1