Cacher is the code snippet organizer for pro developers

class Array
  def <=(value)
    size_self = self.size
    size_value = value.size
    return false if self.size > value.size
    return true if self.size < value.size
    value.each_with_index do |value, i|
      return false if value < self[i]
    end
    return true
  end
end

class Palindrome

  def compute(value)
    @size = value.size
    @even = @size % 2 == 0
    if @even
      @pos1 = (@size/2)-1
      @pos2 = @pos1+1
    else
      @pos1 = (((@size+1)/2)-1)
      @pos2 = @pos1
    end
    @mirrored = value[0..@pos1]
    @start = @even ? @pos1 : @pos2-1
    @mirrored = @mirrored + value[0..@start].reverse
    if @mirrored <= value
            @stack = [] << {:pos1 => @pos1, :pos2 => @pos2}
            while !@stack.empty?
              current_params = @stack.shift
              pos1 = current_params[:pos1]
              pos2 = current_params[:pos2]
                    @pos1 = @mirrored[pos1]
                    if @pos1 < 0
                      @mirrored[@size-1] = 1
                      @mirrored.unshift(1)
                    else
                      if @pos1 < 9
            @mirrored[pos1] = @mirrored[pos2] = (@pos1.to_i + 1)
                      else
            @mirrored[pos1] = @mirrored[pos2] = 0
            @stack << {:pos1 => pos1-1, :pos2 => pos2+1}
                      end
              end
            end
    end
    return @mirrored
  end
end

t = gets.to_i
1.upto(t){
  puts Palindrome.new.compute(gets.unpack("c*").map { |c| c-48}[0...-1]).join
}