Вам задана скобочная последовательность, состоящая из $$$n$$$ символов '(' и/или )'. Вы производите над ней последовательность операций.

В течение одной операции вы выбираете кратчайший префикс этой строки (какое-то количество первых символов строки), который является хорошим, и удаляете его из строки.

Префикс считается хорошим, если выполняется одно из следующих двух условий:

• этот префикс является правильной скобочной последовательностью;
• этот префикс является палиндромом длины хотя бы два.

Скобочная последовательность называется правильной, если из нее возможно получить корректное арифметическое выражение вставкой символов '+' и '1' в эту последовательность. Например, последовательности (())(), () и (()(())) являются правильными, когда )(, (() и (()))( ими не являются.

Скобочная последовательность называется палиндромом, если она читается одинаково и вперед и назад. Например, скобочные последовательности )), (( и )(() являются палиндромами, а скобочные последовательности (), )( и ))( ими не являются.

Вы прекращаете производить операции тогда, когда невозможно найти ни одного хорошего префикса. Ваша задача — найти количество операций, которые вы произведете, а также количество оставшихся в строке символов после всех операций.

Вам необходимо ответить на $$$t$$$ независимых наборов тестовых данных.