### constant

H = 4
W = 8
HW = H * W

### main

gl = []
for y in (0...H)
  for x in (0...W)
    id = y * W + x
    gl[id] = (x < W - 1) ? (y + 1) * 10 + (x + 1) : 0
  end
end
#p gl

n = gets.to_i

n.times do
  gets

  flds = []
  H.times do
    flds += [0] + gets.split.map(&:to_i)
  end
  #p $flds

  gaps = []
  for i in (0...HW)
    next if i % W == 0
    if flds[i] % 10 == 1
      y = flds[i] / 10 - 1
      flds[y * W] = flds[i]
      flds[i] = 0
      gaps << i
    end
  end
  #p flds
  #p gaps

  used = {}
  used[flds] = true
  q = [[0, flds, gaps]]
  gd = nil

  while ! q.empty?
    ud, uflds, ugaps = q.shift

    if uflds == gl
      gd = ud
      break
    end

    vd = ud + 1

    for gi in (0...H)
      vgaps = ugaps.clone
      vgapi = vgaps[gi]

      vflds = uflds.clone
      c = vflds[vgapi - 1] + 1
      vid = vflds.index(c)
      next if vid.nil?

      vflds[vgapi] = c
      vflds[vid] = 0
      vgaps[gi] = vid

      if ! used[vflds]
        used[vflds] = true
        q << [vd, vflds, vgaps]
      end
    end
  end

  puts (gd || -1)
end