fun getMaxBurles(n: Int, k: Int, s: String): Int 
{
    val low = IntArray(26) 
    val up = IntArray(26) 
 
    for (c in s) {
        if (c in 'a'..'z') {
            low[c - 'a']++
        } else {
            up[c - 'A']++
        }
    }
 
    var pairs = 0
    var operation = 0
 
 
    for (i in 0 until 26) 
    {
        val minCount = minOf(low[i], up[i])
        pairs += minCount
        operation += Math.abs(low[i] - up[i]) / 2
    }
 
    val addition = minOf(k, operation) 
    return pairs + addition
}
 
fun main() 
{
    val t = readLine()!!.toInt() 
 
    val results = mutableListOf<Int>()
 
    for (i in 0 until t) 
    {
        val (n, k) = readLine()!!.split(" ").map { it.toInt() } 
        val s = readLine()!! 
        results.add(getMaxBurles(n, k, s))
    }
 
    for (result in results) 
    {
        println(result) 
    }
}
 

ZnVuIGdldE1heEJ1cmxlcyhuOiBJbnQsIGs6IEludCwgczogU3RyaW5nKTogSW50IAp7CiAgICB2YWwgbG93ID0gSW50QXJyYXkoMjYpIAogICAgdmFsIHVwID0gSW50QXJyYXkoMjYpIAoKICAgIGZvciAoYyBpbiBzKSB7CiAgICAgICAgaWYgKGMgaW4gJ2EnLi4neicpIHsKICAgICAgICAgICAgbG93W2MgLSAnYSddKysKICAgICAgICB9IGVsc2UgewogICAgICAgICAgICB1cFtjIC0gJ0EnXSsrCiAgICAgICAgfQogICAgfQoKICAgIHZhciBwYWlycyA9IDAKICAgIHZhciBvcGVyYXRpb24gPSAwCgoKICAgIGZvciAoaSBpbiAwIHVudGlsIDI2KSAKICAgIHsKICAgICAgICB2YWwgbWluQ291bnQgPSBtaW5PZihsb3dbaV0sIHVwW2ldKQogICAgICAgIHBhaXJzICs9IG1pbkNvdW50CiAgICAgICAgb3BlcmF0aW9uICs9IE1hdGguYWJzKGxvd1tpXSAtIHVwW2ldKSAvIDIKICAgIH0KCiAgICB2YWwgYWRkaXRpb24gPSBtaW5PZihrLCBvcGVyYXRpb24pIAogICAgcmV0dXJuIHBhaXJzICsgYWRkaXRpb24KfQoKZnVuIG1haW4oKSAKewogICAgdmFsIHQgPSByZWFkTGluZSgpISEudG9JbnQoKSAKCiAgICB2YWwgcmVzdWx0cyA9IG11dGFibGVMaXN0T2Y8SW50PigpCgogICAgZm9yIChpIGluIDAgdW50aWwgdCkgCiAgICB7CiAgICAgICAgdmFsIChuLCBrKSA9IHJlYWRMaW5lKCkhIS5zcGxpdCgiICIpLm1hcCB7IGl0LnRvSW50KCkgfSAKICAgICAgICB2YWwgcyA9IHJlYWRMaW5lKCkhISAKICAgICAgICByZXN1bHRzLmFkZChnZXRNYXhCdXJsZXMobiwgaywgcykpCiAgICB9CgogICAgZm9yIChyZXN1bHQgaW4gcmVzdWx0cykgCiAgICB7CiAgICAgICAgcHJpbnRsbihyZXN1bHQpIAogICAgfQp9Cg==

NQoxMSAyCmFBYWFCQUNhY2JFCjIgMgphYgo0IDEKYWFCQgo2IDAKYWJCQWNDCjUgMwpjYmNjYgo=

5
11 2
aAaaBACacbE
2 2
ab
4 1
aaBB
6 0
abBAcC
5 3
cbccb