```go
package main

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

func main() {
	reader := bufio.NewReaderSize(os.Stdin, 65536)
	writer := bufio.NewWriterSize(os.Stdout, 65536)
	defer writer.Flush()

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

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

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

		var s string
		fmt.Fscan(reader, &s)

		stack = stack[:0]
		wValues = wValues[:0]

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

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

		var total int64 = 0
		for _, w := range wValues {
			total += int64(w)
		}

		for j := 0; j < k && j < len(wValues); j++ {
			total -= int64(wValues[j])
		}

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