package main

import (
	"bufio"
	"io"
	"os"
	"strconv"
)

const MaxK = 5
const Shift = 5
const INF int64 = 1 << 60

type FastScanner struct {
	data []byte
	idx  int
}

func (fs *FastScanner) skip() {
	n := len(fs.data)
	for fs.idx < n && fs.data[fs.idx] <= ' ' {
		fs.idx++
	}
}

func (fs *FastScanner) nextInt() int {
	fs.skip()
	sign := 1
	if fs.data[fs.idx] == '-' {
		sign = -1
		fs.idx++
	}
	v := 0
	for fs.idx < len(fs.data) && fs.data[fs.idx] > ' ' {
		v = v*10 + int(fs.data[fs.idx]-'0')
		fs.idx++
	}
	return v * sign
}

func (fs *FastScanner) nextBytes() []byte {
	fs.skip()
	start := fs.idx
	for fs.idx < len(fs.data) && fs.data[fs.idx] > ' ' {
		fs.idx++
	}
	return fs.data[start:fs.idx]
}

type State struct {
	m, do, dc, diff int
}

type Precomp struct {
	states             []State
	insO, insC         []int
	delO, delC         []int
	zero               []int
	start              int
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func build(K int) Precomp {
	var idx [MaxK + 1][2*MaxK + 1][2*MaxK + 1]int
	for a := 0; a <= MaxK; a++ {
		for b := 0; b <= 2*MaxK; b++ {
			for c := 0; c <= 2*MaxK; c++ {
				idx[a][b][c] = -1
			}
		}
	}

	states := make([]State, 0)
	for m := 0; m <= K; m++ {
		for do := -m; do <= K; do++ {
			for dc := -m; dc <= K; dc++ {
				if m+max(do, 0)+max(dc, 0) <= K {
					idx[m][do+Shift][dc+Shift] = len(states)
					states = append(states, State{m: m, do: do, dc: dc, diff: do - dc})
				}
			}
		}
	}

	get := func(m, do, dc int) int {
		if m < 0 || m > K || do < -MaxK || do > MaxK || dc < -MaxK || dc > MaxK {
			return -1
		}
		return idx[m][do+Shift][dc+Shift]
	}

	n := len(states)
	insO := make([]int, n)
	insC := make([]int, n)
	delO := make([]int, n)
	delC := make([]int, n)
	for i := 0; i < n; i++ {
		insO[i], insC[i], delO[i], delC[i] = -1, -1, -1, -1
	}

	zero := make([]int, 0)
	for i, st := range states {
		insO[i] = get(st.m, st.do+1, st.dc)
		insC[i] = get(st.m, st.do, st.dc+1)
		delO[i] = get(st.m+1, st.do-1, st.dc)
		delC[i] = get(st.m+1, st.do, st.dc-1)
		if st.do == 0 && st.dc == 0 {
			zero = append(zero, i)
		}
	}

	return Precomp{
		states: states,
		insO:   insO,
		insC:   insC,
		delO:   delO,
		delC:   delC,
		zero:   zero,
		start:  get(0, 0, 0),
	}
}

func closure(dp []int64, pref int, pc *Precomp) {
	states := pc.states
	for i, st := range states {
		val := dp[i]
		if val >= INF {
			continue
		}
		b := pref + st.diff
		if b < 0 {
			continue
		}
		if to := pc.insO[i]; to != -1 {
			nv := val + int64(b)
			if nv < dp[to] {
				dp[to] = nv
			}
		}
		if to := pc.insC[i]; to != -1 && b > 0 {
			if val < dp[to] {
				dp[to] = val
			}
		}
	}
}

func main() {
	data, _ := io.ReadAll(os.Stdin)
	fs := FastScanner{data: data}

	var pcs [MaxK + 1]Precomp
	for k := 0; k <= MaxK; k++ {
		pcs[k] = build(k)
	}

	t := fs.nextInt()
	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	defer out.Flush()

	for ; t > 0; t-- {
		k := fs.nextInt()
		s := fs.nextBytes()
		pc := &pcs[k]
		num := len(pc.states)

		cur := make([]int64, num)
		nxt := make([]int64, num)
		for i := 0; i < num; i++ {
			cur[i] = INF
		}
		cur[pc.start] = 0

		origBal := 0

		for _, ch := range s {
			closure(cur, origBal, pc)

			for i := 0; i < num; i++ {
				nxt[i] = INF
			}

			if ch == '(' {
				for i, st := range pc.states {
					val := cur[i]
					if val >= INF {
						continue
					}
					b := origBal + st.diff
					if b < 0 {
						continue
					}
					nv := val + int64(b)
					if nv < nxt[i] {
						nxt[i] = nv
					}
					if to := pc.delO[i]; to != -1 && val < nxt[to] {
						nxt[to] = val
					}
				}
				origBal++
			} else {
				for i, st := range pc.states {
					val := cur[i]
					if val >= INF {
						continue
					}
					b := origBal + st.diff
					if b < 0 {
						continue
					}
					if b > 0 && val < nxt[i] {
						nxt[i] = val
					}
					if to := pc.delC[i]; to != -1 && val < nxt[to] {
						nxt[to] = val
					}
				}
				origBal--
			}

			cur, nxt = nxt, cur
		}

		closure(cur, 0, pc)

		ans := INF
		for _, idx := range pc.zero {
			if cur[idx] < ans {
				ans = cur[idx]
			}
		}

		out.WriteString(strconv.FormatInt(ans, 10))
		out.WriteByte('\n')
	}
}