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
    if size > 1000
      value = value[0..10]
    end
    value.each_with_index do |v, i|
      return false if v < 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 = @pos2 = (((@size+1)/2)-1)
    end
    @mirrored = value[0..@pos1]
    @start = @even ? @pos1 : @pos2-1
    @mirrored = @mirrored + value[0..@start].reverse if @size > 1
    if @mirrored <= value
            @e = @pos1 == @pos2 ? @pos1 : @pos1+1
            @s = @pos1 == @pos2 ? @pos2 : @pos2-1
            @stack = [] << {:pos1 => @pos1}
            while !@stack.empty?
              current_params = @stack.shift
              pos1 = current_params[:pos1]
                    @pos1 = @mirrored[pos1]
                    if pos1 < 0
                      @mirrored[@size-1] = 1
                      @mirrored.unshift(1)
		      @e = @e+1
                    else
                      if @pos1 < 9
            @mirrored[pos1] = (@pos1 + 1)
                      else
            @mirrored[pos1] = 0
            @stack << {:pos1 => pos1-1}
                      end
              end
            end
    @mirrored[@e..-1] = @mirrored[0..@s].reverse if @size > 1
    end
    return @mirrored
  end
end

t = gets.to_i
while t > 0 
  puts Palindrome.new.compute(gets.unpack("c*").map { |c| c-48}[0...-1]).map { |c| c+48}.pack("c*")
  t = t - 1
end