fun main(args: Array<String>) {
  val bf = java.io.BufferedReader(java.io.InputStreamReader(System.`in`))
  repeat(bf.readLine()!!.toInt()) {
    val n = bf.readLine()!!.toInt()
    val A = generateSequence { bf.readLine()!!.split(" ").map{ it.toInt() }.toList() }.take(n).toList()
    
    data class Edge(val u: Int, val v: Int, val c: Int) : Comparable<Edge>{
      override fun compareTo(other: Edge) = -(this.c - other.c)
    }

    val edges = Array(n * n) { Edge(it / n, it % n, A[it / n][it % n]) }.sorted()

    val grp = Array(n) { it }
    fun go(x: Int): Int {
      if(grp[x] != x) {
        grp[x] = go(grp[x])
      }
      return grp[x]
    }

    var ans = 0L

    for((u, v, c) in edges) {
      val p = go(u)
      val q = go(v)
      if(p != q) {
        val gp = (0 until n).filter{ go(it) == p }.toList()
        val gq = (0 until n).filter{ go(it) == q }.toList()
        for(x in gp) {
          for(y in gq) {
            ans += c - A[x][y]
            ans += c - A[y][x]
          }
        }
        grp[p] = q
      }
    }
    println(ans)
  }
}