```go
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

func main() {
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var t int
	if _, err := fmt.Fscan(reader, &t); err != nil {
		return
	}

	stack := make([]int, 0, 200000)
	weights := make([]int, 0, 200000)

	for i := 0; i < t; i++ {
		var k int
		var s string
		fmt.Fscan(reader, &k, &s)

		stack = stack[:0]
		weights = weights[:0]

		cost := int64(0)

		for j := 0; j < len(s); j++ {
			if s[j] == '(' {
				stack = append(stack, j)
			} else {
				left := stack[len(stack)-1]
				stack = stack[:len(stack)-1]
				
				w := (j - left - 1) / 2
				weights = append(weights, w)
				cost += int64(w)
			}
		}

		sort.Slice(weights, func(a, b int) bool {
			return weights[a] > weights[b]
		})

		limit := k
		if limit > len(weights) {
			limit = len(weights)
		}

		for j := 0; j < limit; j++ {
			cost -= int64(weights[j])
		}

		fmt.Fprintln(writer, cost)
	}
}
```