Вам задана скобочная последовательность, состоящая из \(n\) символов '(' и/или )'. Вы производите над ней последовательность операций.
В течение одной операции вы выбираете кратчайший префикс этой строки (какое-то количество первых символов строки), который является хорошим, и удаляете его из строки.
Префикс считается хорошим, если выполняется одно из следующих двух условий:
- этот префикс является правильной скобочной последовательностью;
- этот префикс является палиндромом длины хотя бы два.
Скобочная последовательность называется правильной, если из нее возможно получить корректное арифметическое выражение вставкой символов '+' и '1' в эту последовательность. Например, последовательности (())(), () и (()(())) являются правильными, когда )(, (() и (()))( ими не являются.
Скобочная последовательность называется палиндромом, если она читается одинаково и вперед и назад. Например, скобочные последовательности )), (( и )(() являются палиндромами, а скобочные последовательности (), )( и ))( ими не являются.
Вы прекращаете производить операции тогда, когда невозможно найти ни одного хорошего префикса. Ваша задача — найти количество операций, которые вы произведете, а также количество оставшихся в строке символов после всех операций.
Вам необходимо ответить на \(t\) независимых наборов тестовых данных.
Выходные данные
На каждый набор тестовых данных выведите два целых числа \(c\) и \(r\) — количество операций, которые вы произведете над данной скобочной последовательностью и количество оставшихся в ней символов после всех операций.