for index in 1..9
i=gets.chomp
b= [*
(
i.chars
.group_by{|x| x}
.group_by{|x,y| y.size}
.map{|x|
s=x[1].size
x[1][0...s-s%2].map{|x| x[0]}*''
}*''
).chars
.each_slice(2)
]
puts [*
[*
b.size
.downto(1)
.map{|n|
b.combination(n)
.map{|t|
[
t*'',
(
h = Hash[t]
s = []
o = 1
i.each_char{|c|
s.push(c) if h.keys.include? c
(
o = false if s.empty? || !h[s.pop].eql?(c)
) if h.values.include? c
}
o ? s.empty? : o
)
]
}
}.find{|x| x[0][1]}
][0]
][0]
end
Zm9yIGluZGV4IGluIDEuLjkKICAgIGk9Z2V0cy5jaG9tcAogICAgYj0gWyoKICAgICAgICAoCiAgICAgICAgICAgIGkuY2hhcnMKICAgICAgICAgICAgICAgIC5ncm91cF9ieXt8eHwgeH0KICAgICAgICAgICAgICAgIC5ncm91cF9ieXt8eCx5fCB5LnNpemV9CiAgICAgICAgICAgICAgICAubWFwe3x4fAogICAgICAgICAgICAgICAgICAgIHM9eFsxXS5zaXplCiAgICAgICAgICAgICAgICAgICAgeFsxXVswLi4ucy1zJTJdLm1hcHt8eHwgeFswXX0qJycKICAgICAgICAgICAgICAgIH0qJycKICAgICAgICApLmNoYXJzCiAgICAgICAgLmVhY2hfc2xpY2UoMikKICAgIF0KCiAgICBwdXRzIFsqCiAgICAgICAgWyoKICAgICAgICAgICAgYi5zaXplCiAgICAgICAgICAgICAgICAuZG93bnRvKDEpCiAgICAgICAgICAgICAgICAubWFwe3xufAogICAgICAgICAgICAgICAgICAgIGIuY29tYmluYXRpb24obikKICAgICAgICAgICAgICAgICAgICAgICAgLm1hcHt8dHwKICAgICAgICAgICAgICAgICAgICAgICAgICAgIFsKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICB0KicnLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICgKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgaCA9IEhhc2hbdF0KICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcyA9IFtdCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIG8gPSAxCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGkuZWFjaF9jaGFye3xjfAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgcy5wdXNoKGMpIGlmIGgua2V5cy5pbmNsdWRlPyBjCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAoCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgbyA9IGZhbHNlIGlmIHMuZW1wdHk/IHx8ICFoW3MucG9wXS5lcWw/KGMpCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICApIGlmIGgudmFsdWVzLmluY2x1ZGU/IGMKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBvID8gcy5lbXB0eT8gOiBvCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgKQogICAgICAgICAgICAgICAgICAgICAgICAgICAgXQogICAgICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICB9LmZpbmR7fHh8IHhbMF1bMV19CiAgICAgICAgXVswXQogICAgXVswXQplbmQ=