Seinfeld

У мене закінчилися історії. Протягом багатьох років я писав історії, деякі досить дурні, лише щоб прості проблеми виглядали складними, а складні проблеми виглядали простими. Але, на жаль, не для цього випадку.

Вам надано непорожній рядок, що складається виключно з відкриваючих і закриваючих дужок. Ваше завдання — визначити мінімальну кількість "операцій", необхідних для того, щоб зробити рядок стабільним. Стабільність визначається так:

1. Порожній рядок є стабільним.

2. Якщо S стабільний, то {S} також стабільний.

3. Якщо S і T обидва стабільні, то ST (конкатенація двох) також стабільний.

Усі ці рядки стабільні: {}, {}{}, і {{}{}}; Але жоден з цих: }{, {{}{, ні {}{.

Єдина операція, дозволена над рядком, — це заміна відкриваючої дужки на закриваючу, або навпаки.

Вхідні дані

Ваша програма буде протестована на одному або більше наборах даних. Кожен набір даних описується в одному рядку. Рядок є непорожнім і складається з відкриваючих і закриваючих дужок і нічого іншого. Жоден рядок не має більше 2000 дужок. Усі послідовності мають парну довжину.

Останній рядок введення складається з одного або більше "-" (мінусів).

Вихідні дані

Для кожного тестового випадку виведіть наступний рядок:

k.N

Де k — номер тестового випадку (починаючи з одного), а N — мінімальна кількість операцій, необхідних для перетворення даного рядка в збалансований.

Приклади