MAX = 8
INIT = "1 1 1 1 1 1 1 1 1 2 2 2 4 4 4 6 6 6 5 5 5 3 3 3 3 3 3 3 3 3"
LEFT, RIGHT, TOP, BOTTOM = (0..3).to_a

def rotate(cube, direction)
  swap = Array.new
  case direction
    when LEFT
      swap << [1, 24] << [4, 27] << [7, 30] << [10, 21] << [16, 18]
    when RIGHT
      swap << [3, 22] << [6, 25] << [9, 28] << [12, 19] << [13, 15]
    when TOP
      swap << [1, 28] << [2, 29] << [3, 30] << [15, 16] << [19, 21]
    when BOTTOM
      swap << [7, 22] << [8, 23] << [9, 24] << [13, 18] << [10, 12]
  end
  swap.map!{|i, j| [i - 1, j - 1]}

  result = cube.split
  swap.each do |i, j|
    result[i], result[j] = result[j], result[i]
  end
  result*" "
end

def bfs(init, limit)
  memo = Hash.new
  q = Array.new << [0, init]
  until q.empty?
    depth, cube = q.shift
    break if limit < depth
    memo[cube] = depth unless memo[cube]
    memo[cube] = [memo[cube], depth].min
    [LEFT, RIGHT, TOP, BOTTOM].each do |d|
      q << [depth + 1, rotate(cube, d)]
    end
  end
  memo
end

memo = bfs(INIT, MAX / 2)
gets.to_i.times do
  memo2 = bfs(gets.chomp, MAX / 2)
  p memo.each.map{|key, value| value + (memo2[key] ? memo2[key] : MAX)}.min
end