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

Zm9yIGluZGV4IGluIDEuLjkKICAgIGlucHV0PWdldHMuY2hvbXAKICAgIGJyYWNlcz0oCiAgICAgICAgaW5wdXQuY2hhcnMKICAgICAgICAgICAgLmdyb3VwX2J5e3xjaGFyfCBjaGFyfQogICAgICAgICAgICAuZ3JvdXBfYnl7fGNoYXIsY2hhckFycmF5fCBjaGFyQXJyYXkuc2l6ZX0KICAgICAgICAgICAgLm1hcHt8aGFzaHBhaXJ8CiAgICAgICAgICAgICAgICBjaGFyQ291bnQ9aGFzaHBhaXJbMV0uc2l6ZQogICAgICAgICAgICAgICAgaGFzaHBhaXJbMV1bMC4uLmNoYXJDb3VudCAtIGNoYXJDb3VudCAlIDJdLm1hcHt8eHwgeFswXX0uam9pbgogICAgICAgICAgICB9LmpvaW4KICAgICkuY2hhcnMKICAgIC5lYWNoX3NsaWNlKDIpCiAgICAudG9fYQoKICAgIHB1dHMgYnJhY2VzLnNpemUKICAgICAgICAuZG93bnRvKDEpCiAgICAgICAgLm1hcHt8bnwKICAgICAgICAgICAgYnJhY2VzLmNvbWJpbmF0aW9uKG4pCiAgICAgICAgICAgICAgICAubWFwe3xjb21ib3wKICAgICAgICAgICAgICAgICAgICBbCiAgICAgICAgICAgICAgICAgICAgICAgIGNvbWJvLmpvaW4sCiAgICAgICAgICAgICAgICAgICAgICAgICgKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGNvbWJvSGFzaCA9IEhhc2hbY29tYm9dCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBzdGFjayA9IFtdCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBvdXRwdXQgPSAxCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBpbnB1dC5lYWNoX2NoYXJ7fGNoYXJ8CiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgc3RhY2sucHVzaChjaGFyKSBpZiBjb21ib0hhc2gua2V5cy5pbmNsdWRlPyBjaGFyCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgKAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBvdXRwdXQgPSBmYWxzZSBpZiBzdGFjay5lbXB0eT8gfHwgIWNvbWJvSGFzaFtzdGFjay5wb3BdLmVxbD8oY2hhcikKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICApIGlmIGNvbWJvSGFzaC52YWx1ZXMuaW5jbHVkZT8gY2hhcgogICAgICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgICAgICAgICAgb3V0cHV0ID8gc3RhY2suZW1wdHk/IDogb3V0cHV0CiAgICAgICAgICAgICAgICAgICAgICAgICkKICAgICAgICAgICAgICAgICAgICBdCiAgICAgICAgICAgICAgICB9CiAgICAgICAgfS5maW5ke3x4fCB4WzBdWzFdfQogICAgICAgIC50b19hWzBdCiAgICAgICAgLnRvX2FbMF0KZW5k

YWJjYwpmZmZmZgphZWRiZWRlYmRjZWNkZWMKYWJjZAphYWJiY2MKYWJjCmFiYmFjCmFhYmNkYgphYmNkYWNiZA==

abcc
fffff
aedbedebdcecdec
abcd
aabbcc
abc
abbac
aabcdb
abcdacbd