for index in 1..9
    input=gets.chomp
    braces=(
        input.chars
            .group_by{|char| char}
            .group_by{|char,charArray| charArray.size}
            .map{|hashpair|
                charCount=hashpair[1].size
                hashpair[1][0...charCount - charCount % 2].map{|x| x[0]}.join
            }.join
    ).chars
    .each_slice(2)
    .to_a

    puts braces.size
        .downto(1)
        .map{|n|
            braces.combination(n)
                .map{|combo|
                    [
                        combo.join,
                        (
                            comboHash = Hash[combo]
                            stack = []
                            output = 1
                            input.each_char{|char|
                                stack.push(char) if comboHash.keys.include? char
                                (
                                    output = false if stack.empty? || !comboHash[stack.pop].eql?(char)
                                ) if comboHash.values.include? char
                            }
                            output ? stack.empty? : output
                        )
                    ]
                }
        }.find{|x| x[0][1]}
        .to_a[0]
        .to_a[0]
end