скобочные последовательности (возможно)

Известно, что в правильной последовательности содержатся пары, состоящие из заглавных и строчных вариаций одной и той же буквы, притом данные пары должны обеспечивать последовательную вложенность внутри общей строки. Примеры правильных сообщений:

йцукенгшщЩШГзЗНЕКУЦмМЙаА
фыЫваАВФ
ячсмиИтьЬТМСЧЯхХ

Примеры неправильных сообщений:

фЫываАВФ
чясмиИтьЬТМСЧЯчХ

Формат входных данных.
Число n (1 < п $ 10000) - число сообщений, среди которых нужно найти правильные.

Данные: по одному в строке даны сообщения, в форме строк, состоящих из строчных и заглавных букв алфавита, длина каждого сообщения не превышает 10000 символов.

Формат выходных данных.
Для каждой строки нужно вывести в консоль "0", если строка неправильная, или вывести в консоль "1" если строка правильная. В голову не приходит, как можно реализовать это, заранее спасибо.