fun main(args: Array<String>) {
    if(args.isNotEmpty()) {
        System.setIn(java.io.FileInputStream(args[0]))
    }
 
    val numTests = readLine()!!.toInt()
    require(numTests in 1..5)
 
    var sumN = 0
    repeat(numTests) {
        val (N, K) = readLine()!!.split(" ").map{ it.toInt() }
        require(N in 1..20)
        require(K in 3..N)
 
        sumN += N
        require(sumN <= 20)
 
        val W = List(N) { readLine()!!.split(" ").map{ it.toInt() } }
        require((0 until N).all{ W[it][it] == 0 })
        require((1 until N).all{ i -> (0 until i).all{ j -> W[i][j] == W[j][i] } })
        require((1 until N).all{ i -> (0 until i).all{ j -> W[i][j] in 1..1000000 } })
 
        val edgesum = IntArray(1 shl N)
        for(mask in 1 until (1 shl N)) {
            val i = Integer.bitCount(Integer.lowestOneBit(mask) - 1)
            var sum = 0
            for(j in 0 until N) if((mask shr j) and 1 == 1) sum += W[i][j]
            edgesum[mask] = edgesum[mask xor (1 shl i)] + sum
        }
 
        // 3^(N-K) * (K-2) <= 3^17
        val dp = IntArray(1 shl (N-K)) { mask -> edgesum[(mask shl K) or 1] }
        for(u in 1 until K) {
            for(mask in (1 shl (N-K)) - 1 downTo 0) {
                var submask = mask
                var now = dp[mask]
                while(submask > 0) {
                    now = maxOf(dp[mask xor submask] + edgesum[(submask shl K) or (1 shl u)], now)
                    submask = (submask - 1) and mask
                }
                dp[mask] = now
                if(u == K-1) break
            }
        }
        println(W.map{ it.sum() }.sum() / 2 - dp.max()!!)
    }
}

ZnVuIG1haW4oYXJnczogQXJyYXk8U3RyaW5nPikgewogICAgaWYoYXJncy5pc05vdEVtcHR5KCkpIHsKICAgICAgICBTeXN0ZW0uc2V0SW4oamF2YS5pby5GaWxlSW5wdXRTdHJlYW0oYXJnc1swXSkpCiAgICB9CgogICAgdmFsIG51bVRlc3RzID0gcmVhZExpbmUoKSEhLnRvSW50KCkKICAgIHJlcXVpcmUobnVtVGVzdHMgaW4gMS4uNSkKCiAgICB2YXIgc3VtTiA9IDAKICAgIHJlcGVhdChudW1UZXN0cykgewogICAgICAgIHZhbCAoTiwgSykgPSByZWFkTGluZSgpISEuc3BsaXQoIiAiKS5tYXB7IGl0LnRvSW50KCkgfQogICAgICAgIHJlcXVpcmUoTiBpbiAxLi4yMCkKICAgICAgICByZXF1aXJlKEsgaW4gMy4uTikKCiAgICAgICAgc3VtTiArPSBOCiAgICAgICAgcmVxdWlyZShzdW1OIDw9IDIwKQoKICAgICAgICB2YWwgVyA9IExpc3QoTikgeyByZWFkTGluZSgpISEuc3BsaXQoIiAiKS5tYXB7IGl0LnRvSW50KCkgfSB9CiAgICAgICAgcmVxdWlyZSgoMCB1bnRpbCBOKS5hbGx7IFdbaXRdW2l0XSA9PSAwIH0pCiAgICAgICAgcmVxdWlyZSgoMSB1bnRpbCBOKS5hbGx7IGkgLT4gKDAgdW50aWwgaSkuYWxseyBqIC0+IFdbaV1bal0gPT0gV1tqXVtpXSB9IH0pCiAgICAgICAgcmVxdWlyZSgoMSB1bnRpbCBOKS5hbGx7IGkgLT4gKDAgdW50aWwgaSkuYWxseyBqIC0+IFdbaV1bal0gaW4gMS4uMTAwMDAwMCB9IH0pCgogICAgICAgIHZhbCBlZGdlc3VtID0gSW50QXJyYXkoMSBzaGwgTikKICAgICAgICBmb3IobWFzayBpbiAxIHVudGlsICgxIHNobCBOKSkgewogICAgICAgICAgICB2YWwgaSA9IEludGVnZXIuYml0Q291bnQoSW50ZWdlci5sb3dlc3RPbmVCaXQobWFzaykgLSAxKQogICAgICAgICAgICB2YXIgc3VtID0gMAogICAgICAgICAgICBmb3IoaiBpbiAwIHVudGlsIE4pIGlmKChtYXNrIHNociBqKSBhbmQgMSA9PSAxKSBzdW0gKz0gV1tpXVtqXQogICAgICAgICAgICBlZGdlc3VtW21hc2tdID0gZWRnZXN1bVttYXNrIHhvciAoMSBzaGwgaSldICsgc3VtCiAgICAgICAgfQoKICAgICAgICAvLyAzXihOLUspICogKEstMikgPD0gM14xNwogICAgICAgIHZhbCBkcCA9IEludEFycmF5KDEgc2hsIChOLUspKSB7IG1hc2sgLT4gZWRnZXN1bVsobWFzayBzaGwgSykgb3IgMV0gfQogICAgICAgIGZvcih1IGluIDEgdW50aWwgSykgewogICAgICAgICAgICBmb3IobWFzayBpbiAoMSBzaGwgKE4tSykpIC0gMSBkb3duVG8gMCkgewogICAgICAgICAgICAgICAgdmFyIHN1Ym1hc2sgPSBtYXNrCiAgICAgICAgICAgICAgICB2YXIgbm93ID0gZHBbbWFza10KICAgICAgICAgICAgICAgIHdoaWxlKHN1Ym1hc2sgPiAwKSB7CiAgICAgICAgICAgICAgICAgICAgbm93ID0gbWF4T2YoZHBbbWFzayB4b3Igc3VibWFza10gKyBlZGdlc3VtWyhzdWJtYXNrIHNobCBLKSBvciAoMSBzaGwgdSldLCBub3cpCiAgICAgICAgICAgICAgICAgICAgc3VibWFzayA9IChzdWJtYXNrIC0gMSkgYW5kIG1hc2sKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIGRwW21hc2tdID0gbm93CiAgICAgICAgICAgICAgICBpZih1ID09IEstMSkgYnJlYWsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICBwcmludGxuKFcubWFweyBpdC5zdW0oKSB9LnN1bSgpIC8gMiAtIGRwLm1heCgpISEpCiAgICB9Cn0=