foo.rb

class Array

  def <=(value)
    @self_size = self.size
    @value_size= value.size
    return false if @self_size > @value_size
    tmp = true
    for iterator in @self_size-1..0
      tmp = false if self[iterator] > value[iterator]
    end	 
    return tmp
  end
end

class Foo

  def compute(value)
    @input_array = value
    @size = @input_array.size
    @even = @size % 2 == 0
    if @even
      @position_one = (@size/2)-1
      @position_two = @position_one+1
    else
      @position_one = (((@size+1)/2)-1)
      @position_two = @position_one
    end
    @mirrored = @input_array[0..@position_one]
    @start = @even ? @position_one : @position_two-1
    for i in @start..0
      @mirrored << @input_array[i]
    end
    if @mirrored <= value
      nxt(@position_one, @position_two)
    end
    @mirrored.collect! {|c| c+48}
    STDOUT.write(@mirrored.pack("c*"))
    STDOUT.write("\n")
  end
  def nxt(position_one, position_two)
    if position_one < 0
      @mirrored[@size-1] = 1
      @mirrored.unshift(1)
    else 
      @mirrored_position_one = @mirrored[position_one]
      if @mirrored_position_one < 9
        @mirrored[position_one] = @mirrored[position_two] = @mirrored_position_one + 1
      else
        @mirrored[position_one] = @mirrored[position_two] = 0
        nxt(position_one-1, position_two+1)
      end
    end
  end

end

t = gets.to_i
f = Foo.new
for z in 1..t
  k = STDIN.gets.unpack("c*").collect { |c| c-48}
  k = k[0...-1]
  f.compute(k)
end