You are fed up with your messy room, so you decided to clean it up.

Your room is a bracket sequence $s=s_{1}s_{2}\dots s_{n}$ of length $n$. Each character of this string is either an opening bracket '(' or a closing bracket ')'.

In one operation you can choose any consecutive substring of $s$ and reverse it. In other words, you can choose any substring $s[l \dots r]=s_l, s_{l+1}, \dots, s_r$ and change the order of elements in it into $s_r, s_{r-1}, \dots, s_{l}$.

For example, if you will decide to reverse substring $s[2 \dots 4]$ of string $s=$"((()))" it will be equal to $s=$"()(())".

A regular (aka balanced) bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters '1' and '+' between the original characters of the sequence. For example, bracket sequences "()()", "(())" are regular (the resulting expressions are: "(1)+(1)", "((1+1)+1)"), and ")(" and "(" are not.

A prefix of a string $s$ is a substring that starts at position $1$. For example, for $s=$"(())()" there are $6$ prefixes: "(", "((", "(()", "(())", "(())(" and "(())()".

In your opinion, a neat and clean room $s$ is a bracket sequence that:

  the whole string $s$ is a regular bracket sequence;  and there are exactly $k$ prefixes of this sequence which are regular (including whole $s$ itself). 

For example, if $k = 2$, then "(())()" is a neat and clean room.

You want to use at most $n$ operations to make your room neat and clean. Operations are applied one after another sequentially.

It is guaranteed that the answer exists. Note that you do not need to minimize the number of operations: find any way to achieve the desired configuration in $n$ or less operations.


-----Input-----

The first line contains integer number $t$ ($1 \le t \le 100$) — the number of test cases in the input. Then $t$ test cases follow.

The first line of a test case contains two integers $n$ and $k$ ($1 \le k \le \frac{n}{2}, 2 \le n \le 2000$, $n$ is even) — length of $s$ and required number of regular prefixes.

The second line of a test case contains $s$ of length $n$ — the given bracket sequence. It contains only '(' and ')'.

It is guaranteed that there are exactly $\frac{n}{2}$ characters '(' and exactly $\frac{n}{2}$ characters ')' in the given string.

The sum of all values $n$ over all the test cases in the input doesn't exceed $2000$.


-----Output-----

For each test case print an answer.

In the first line print integer $m$ ($0 \le m \le n$) — the number of operations. You do not need to minimize $m$, any value is suitable.

In the following $m$ lines print description of the operations, each line should contain two integers $l,r$ ($1 \le l \le r \le n$), representing single reverse operation of $s[l \dots r]=s_{l}s_{l+1}\dots s_{r}$. Operations are applied one after another sequentially.

The final $s$ after all operations should be a regular, also it should be exactly $k$ prefixes (including $s$) which are regular.

It is guaranteed that the answer exists. If there are several possible answers you can print any.


-----Example-----
Input
4
8 2
()(())()
10 3
))()()()((
2 1
()
2 1
)(

Output
4
3 4
1 1
5 8
2 2
3
4 10
1 4
6 7
0
1
1 2



-----Note-----

In the first example, the final sequence is "()(()())", where two prefixes are regular, "()" and "()(()())". Note, that all the operations except "5 8" in the example output are useless (they do not change $s$).

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Starter code:

Solutions:
def getOpen(i, st):
	for j in range(i, len(st)):
		if st[j] == '(':
			r = st[j]
			st[j] = st[i]
			st[i] = r
			return j

def getClose(i, st):
	for j in range(i, len(st)):
		if st[j] == ')':
			r = st[j]
			st[j] = st[i]
			st[i] = r
			return j

def test(testStr, k, ans):
	ans = []
	for i in range(k * 2):
		if i % 2 == 0:
			ans.append([i + 1, getOpen(i, testStr) + 1])
		else:
			ans.append([i + 1, getClose(i, testStr) + 1])
	countEteration = (len(testStr) - k * 2) // 2
	for i in range(k * 2, k * 2 + countEteration):
		ans.append([i + 1, getOpen(i, testStr) + 1])
	return ans
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	testStr = input()
	ans = test(list(testStr), k - 1, [])
	print(len(ans))
	for i in range(len(ans)):
		print(' '.join(list(map(str, ans[i]))))


a = int(input())

def fixer(s, index, ans, g1):
	for j in range(index, len(g1)):
		if g1[j] == s:
			ans.append([index + 1, j + 1])
			m = g1[index:j + 1]
			m.reverse()
			for t in range(len(m)):
				g1[t + index] = m[t]
			break
for i in range(a):
	(n, k) = map(int, input().split())
	s = input()
	ans = []
	g1 = []
	index = 0
	for i in range(len(s)):
		g1.append(s[i])
	m = len(s) // 2
	for i in range(k - 1):
		fixer('(', index, ans, g1)
		index += 1
		fixer(')', index, ans, g1)
		index += 1
		m -= 1
	while m:
		m -= 1
		fixer('(', index, ans, g1)
		index += 1
	print(len(ans))
	for i in range(len(ans)):
		print(ans[i][0], ans[i][1])


t = int(input())
for test_i in range(t):
	(n, k) = map(int, input().split())
	s = list(input())
	ans = []
	for i in range(k - 1):
		if s[2 * i] != '(':
			i0 = s.index('(', 2 * i)
			ans.append((2 * i + 1, i0 + 1))
			(s[2 * i], s[i0]) = ('(', ')')
		if s[2 * i + 1] != ')':
			i0 = s.index(')', 2 * i + 1)
			ans.append((2 * i + 2, i0 + 1))
			(s[2 * i + 1], s[i0]) = (')', '(')
	for i in range(n // 2 - k + 1):
		if s[2 * (k - 1) + i] != '(':
			i0 = s.index('(', 2 * (k - 1) + i)
			ans.append((2 * (k - 1) + i + 1, i0 + 1))
			(s[2 * (k - 1) + i], s[i0]) = ('(', ')')
	print(len(ans))
	for pair in ans:
		print(*pair)


t = int(input())
for i in range(t):
	[n, K] = [int(i) for i in input().split()]
	s = input()
	arr = [s[i] for i in range(n)]
	ans = []
	for j in range(n // 2):
		if arr[j] != '(':
			k = j + 1
			while arr[k] != '(':
				k += 1
			ans.append([j + 1, k + 1])
			for l in range(0, (k - j + 1) // 2):
				d = arr[j + l]
				arr[j + l] = arr[k - l]
				arr[k - l] = d
	have = n // 2
	for j in range(K - 1):
		x = j * 2 + 1
		y = x + 1
		while arr[y] != ')':
			y += 1
		ans.append([x + 1, y + 1])
		for l in range(0, (y - x) // 2):
			d = arr[x + l]
			arr[x + l] = arr[y - l]
			arr[y - l] = d
	print(len(ans))
	for j in ans:
		print(j[0], j[1])


t = int(input())
for tt in range(t):
	(n, k) = map(int, input().split())
	s = input()
	ans = []
	if s[0] == ')':
		for i in range(n):
			if s[i] == '(':
				ans.append([1, i + 1])
				s = s[i::-1] + s[i + 1:]
				break
	for i in range(1, (k - 1) * 2):
		if i % 2 == 0:
			if s[i] != '(':
				for j in range(i + 1, n):
					if s[j] == '(':
						ans.append([i + 1, j + 1])
						s = s[:i] + s[j:i - 1:-1] + s[j + 1:]
						break
		elif s[i] != ')':
			for j in range(i + 1, n):
				if s[j] == ')':
					ans.append([i + 1, j + 1])
					s = s[:i] + s[j:i - 1:-1] + s[j + 1:]
					break
	for i in range((k - 1) * 2, (n + 2 * (k - 1)) // 2 + 1):
		if s[i] != '(':
			for j in range(i + 1, n):
				if s[j] == '(':
					ans.append([i + 1, j + 1])
					s = s[:i] + s[j:i - 1:-1] + s[j + 1:]
					break
	print(len(ans))
	for i in ans:
		print(*i)


t = int(input())
while t:
	(n, k) = list(map(int, input().split()))
	s = list(input())
	hyp = []
	k1 = k
	while k - 1:
		hyp.append('(')
		hyp.append(')')
		k -= 1
	ll = n // 2 - (k1 - 1)
	for i in range(ll):
		hyp.append('(')
	for i in range(ll):
		hyp.append(')')
	ans = []
	for i in range(n):
		if hyp[i] != s[i]:
			l = []
			c = 0
			for j in range(i, n):
				l.append(s[j])
				c += 1
				if s[j] == hyp[i]:
					ans.append(i + 1)
					ans.append(j + 1)
					break
			k = i
			for l2 in range(c - 1, -1, -1):
				s[k] = l[l2]
				k += 1
	l3 = len(ans) // 2
	print(l3)
	j = 0
	for i in range(l3):
		print(ans[j], ans[j + 1])
		j += 2
	t -= 1


def openBracket(i):
	global firstOpen, ans
	ind = index[0][firstOpen]
	a = s[i:ind + 1]
	a.reverse()
	s[i:ind + 1] = a
	ans += [[i + 1, ind + 1]]
	firstOpen += 1

def closeBracket(i):
	global firstClose, ans
	ind = index[1][firstClose]
	a = s[i:ind + 1]
	a.reverse()
	ans += [[i + 1, ind + 1]]
	s[i:ind + 1] = a
	firstClose += 1
t = int(input())
for h in range(t):
	(n, k) = map(int, input().split())
	s = list(input())
	ans = []
	fl = 0
	index = [[], []]
	firstOpen = 0
	firstClose = 0
	for i in range(n):
		if s[i] == '(':
			index[0] += [i]
		else:
			index[1] += [i]
	for i in range(2 * k - 2):
		if fl == 0:
			if s[i] != '(':
				openBracket(i)
			else:
				firstOpen += 1
		elif fl == 1:
			if s[i] != ')':
				closeBracket(i)
			else:
				firstClose += 1
		fl = abs(fl - 1)
	fl = 0
	for i in range(2 * k - 2, n):
		if fl == 0:
			if s[i] != '(':
				openBracket(i)
			else:
				firstOpen += 1
		elif fl == 1:
			if s[i] != ')':
				closeBracket(i)
			else:
				firstClose += 1
		if i == n // 2 - k + 2 * k - 2:
			fl = 1
	print(len(ans))
	[print(*i) for i in ans]


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	st = '2' + input()
	ans = []
	forw_b = [0]
	back_b = [0]
	for i in range(1, n + 1):
		if st[i] == '(':
			forw_b.append(i)
		else:
			back_b.append(i)
	indx = [0] + [i for i in range(1, n, 2)]
	for i in range(1, k):
		if forw_b[i] > back_b[i]:
			ans.append([indx[i], max(back_b[i], forw_b[i])])
		else:
			ans.append([indx[i] + 1, max(back_b[i], forw_b[i])])
	l = indx[k]
	q = k
	for i in range(indx[k], n, 2):
		ans.append([l, max(l, forw_b[q])])
		q += 1
		l += 1
	print(len(ans))
	for i in ans:
		print(i[0], i[1])


data = []
l = 0
ans = []

def do(i):
	for g in range(i, l):
		if data[g] != data[i]:
			for j in range((g + 1 - i) // 2):
				(data[i + j], data[g - j]) = (data[g - j], data[i + j])
			ans.append([i + 1, g + 1])
			break
for _ in range(int(input())):
	(l, k) = list(map(int, input().split()))
	data = list(input())
	ans = []
	for i in range((l - (k - 1) * 2) // 2):
		if data[i] != '(':
			do(i)
	for i in range((l - (k - 1) * 2) // 2, l - (k - 1) * 2):
		if data[i] != ')':
			do(i)
	for i in range(l - (k - 1) * 2, l, 2):
		if data[i] != '(':
			do(i)
		if data[i + 1] != ')':
			do(i + 1)
	print(len(ans))
	for i in range(len(ans)):
		print(*ans[i])


for _ in range(int(input())):
	(n, k) = tuple(map(int, input().split()))
	s = list(input())
	ans = list('()' * (k - 1) + '(' * (n // 2 - k + 1) + ')' * (n // 2 - k + 1))
	ops = []
	i = 0
	while ans != s and i < n:
		if ans[i] != s[i]:
			j = s[i:].index(ans[i]) + i
			ops.append(str(i + 1) + ' ' + str(j + 1))
			for k in range(i, (j + i + 1) // 2):
				(s[k], s[j + i - k]) = (s[j + i - k], s[k])
		i += 1
	print(len(ops))
	if len(ops) != 0:
		print('\n'.join(ops))


import os
from io import BytesIO, IOBase
import sys

def reverse(s, x, y):
	(i, j) = (x, y)
	while i < j:
		(s[i], s[j]) = (s[j], s[i])
		(i, j) = (i + 1, j - 1)

def main():
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		s = list(input().rstrip())
		(ans, a) = ([], ['(', ')'])
		for i in range(2 * k - 1):
			if s[i] == a[i & 1]:
				continue
			for j in range(i + 1, n, 1):
				if s[j] == a[i & 1]:
					reverse(s, i, j)
					ans.append((i + 1, j + 1))
					break
		if s[-1] != ')':
			for j in range(n - 1, -1, -1):
				if s[j] == ')':
					reverse(s, j, n - 1)
					ans.append((j + 1, n))
					break
		z = (n - 2 * k) // 2
		for i in range(2 * k - 1, 2 * k - 1 + z, 1):
			if s[i] == '(':
				continue
			for j in range(i + 1, n, 1):
				if s[j] == '(':
					reverse(s, i, j)
					ans.append((i + 1, j + 1))
					break
		print(len(ans))
		for i in ans:
			print(*i)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	st = input()
	s = [st[i] for i in range(n)]
	res = '()' * (k - 1) + '(' * ((n - 2 * (k - 1)) // 2) + ')' * ((n - 2 * (k - 1)) // 2)
	ans = []
	for i in range(n):
		if s[i] != res[i]:
			for j in range(i + 1, n):
				if res[i] == s[j]:
					ans.append([i + 1, j + 1])
					sub = s[i:j + 1]
					sub = sub[::-1]
					for k in range(len(sub)):
						s[i + k] = sub[k]
					break
	print(len(ans))
	for i in range(len(ans)):
		print(ans[i][0], ans[i][1])


from __future__ import print_function
from collections import *
from sys import stdin
import sys
from heapq import *
from math import log2, ceil, sqrt, gcd, log
g = lambda : stdin.readline().strip()
gl = lambda : g().split()
gil = lambda : [int(var) for var in gl()]
gfl = lambda : [float(var) for var in gl()]
gcl = lambda : list(g())
gbs = lambda : [int(var) for var in g()]
rr = lambda x: reversed(range(x))
mod = int(1000000000.0) + 7
inf = float('inf')
(t,) = gil()

def rev(s, i, j, ans):
	ans.append(str(i + 1) + ' ' + str(j + 1))
	for d in range((j - i + 1) // 2):
		(s[i + d], s[j - d]) = (s[j - d], s[i + d])

def getchar(s, i, ch):
	while s[i] != ch:
		i += 1
	return i

def solve(s, n, k):
	l = n // 2 - k + 1
	ans = []
	req = (k - 1) * '()' + l * '(' + l * ')'
	for i in range(n):
		if s[i] != req[i]:
			rev(s, i, getchar(s, i + 1, req[i]), ans)
	print(len(ans))
	if ans:
		print('\n'.join(ans))
for _ in range(t):
	(n, k) = gil()
	s = gcl()
	solve(s, n, k)


t = int(input())
for r in range(t):
	(n, k) = map(int, input().split())
	k -= 1
	want = '()' * k + '(' * (n // 2 - k) + ')' * (n // 2 - k)
	have = input()
	prn = []
	for w in range(len(want)):
		if have[w] != want[w]:
			e = w + have[w:].index(want[w])
			have = have[:w] + have[w:e + 1][::-1] + have[e + 1:]
			prn += [[w + 1, e + 1]]
	print(len(prn))
	for w in prn:
		print(*w)


t = int(input())

def conv1(v):
	global z
	(index, q) = (0, 0)
	for i in range(len(v)):
		if v[i] == '(':
			q += 1
		else:
			q -= 1
		if q == 0 and v[i] == '(':
			if i != len(v):
				v = v[:index] + list(reversed(v[index:i + 1])) + v[i + 1:]
			else:
				v = v[:index] + list(reversed(v[index:i + 1]))
			z.append([index + 1, i + 1])
			index = i + 1
		elif q == 0:
			index = i + 1
	return v

def count(v):
	(q, k) = (0, 0)
	for i in v:
		if i == '(':
			q += 1
		else:
			q -= 1
		if q == 0:
			k += 1
	return k

def conv_min(v, k, n):
	global z
	q = 0
	for i in range(0, len(v)):
		if k == n:
			return v
		if v[i] == '(':
			q += 1
		else:
			q -= 1
		if q == 0:
			z.append([i + 1, i + 2])
			n -= 1

def conv_max(v, k, n):
	global z
	q = 0
	for i in range(0, len(v)):
		if k == n:
			return v
		if v[i] == '(':
			q += 1
		elif q == 2:
			(v[i - 1], v[i]) = (v[i], v[i - 1])
			q = 1
			z.append([i, i + 1])
			n += 1
		elif q > 2:
			(v[i - q + 1], v[i]) = (v[i], v[i - q + 1])
			z.append([i - q + 1, i + 1])
			z.append([i - q + 1, i - q + 2])
			q -= 1
			n += 1
		else:
			q = 0
if 1 == 2:
	s = list('()(())')
	z = []
	print(''.join(conv_max(s, 3, 2)))
	raise SystemExit
for _ in range(t):
	(_, k) = map(lambda x: int(x), input().split())
	s = list(input())
	z = []
	s = conv1(s)
	ct = count(s)
	if ct >= k:
		conv_min(s, k, ct)
	else:
		conv_max(s, k, ct)
	print(len(z))
	print('\n'.join(list(map(lambda x: str(x[0]) + ' ' + str(x[1]), z))))


t = int(input())
for i3 in range(t):
	(n, k) = map(int, input().split())
	inp = str(input())
	(s, ans, x) = ([], [], [])
	for i in range(n):
		x.append(inp[i])
	for i in range(k - 1):
		s.append('(')
		s.append(')')
	for i in range(n // 2 - k + 1):
		s.append('(')
	for i in range(n // 2 - k + 1):
		s.append(')')
	for i in range(n):
		if x[i] == s[i]:
			pass
		else:
			temp = []
			for i2 in range(i, n):
				temp.append(x[i])
				if x[i2] == s[i]:
					ans.append([i + 1, i2 + 1])
					temp.reverse()
					for i3 in range(i, i2 + 1):
						x[i3] = temp[i3 - i]
					break
	print(len(ans))
	for i in range(len(ans)):
		print(ans[i][0], ans[i][1])


from math import *
from collections import *
import sys
sys.setrecursionlimit(10 ** 9)
test = int(input())
for y in range(test):
	(n, k) = map(int, input().split())
	k -= 1
	s = list(input())
	t = ''
	for i in range(k):
		t += '()'
	for i in range(n // 2 - k):
		t += '('
	for i in range(n // 2 - k):
		t += ')'
	print(n)
	for i in range(n):
		j = i
		while s[j] != t[i]:
			j += 1
		(s[i], s[j]) = (s[j], s[i])
		print(i + 1, j + 1)


for T in range(int(input())):
	(n, k) = list(map(int, input().split()))
	s = input()
	lp = 0
	rp = 0
	l = []
	for i in range(k * 2 - 2):
		while lp < n and s[lp] != '(' or lp < i:
			lp += 1
		while rp < n and s[rp] != ')' or rp < i:
			rp += 1
		if i % 2 == 0 and s[i] == '(' or (i % 2 == 1 and s[i] == ')'):
			continue
		elif i % 2 == 0:
			lp += 1
			s = s[:i] + s[i:lp][::-1] + s[lp:]
			l.append([i + 1, lp])
			rp = i
		else:
			rp += 1
			s = s[:i] + s[i:rp][::-1] + s[rp:]
			l.append([i + 1, rp])
			lp = i
	for i in range(k * 2 - 2, (n + k + k - 2) // 2):
		while lp < n and s[lp] != '(' or lp < i:
			lp += 1
		while rp < n and s[rp] != ')' or rp < i:
			rp += 1
		if i < (n + k + k - 2) // 2 and s[i] == '(' or (i >= (n + k + k - 2) // 2 and s[i] == ')'):
			continue
		elif i < (n + k + k) // 2:
			lp += 1
			s = s[:i] + s[i:lp][::-1] + s[lp:]
			l.append([i + 1, lp])
			rp = i
		else:
			rp += 1
			s = s[:i] + s[i:rp][::-1] + s[rp:]
			l.append([i + 1, rp])
			lp = i
	print(len(l))
	for i in l:
		print(*i)


def craftIdeal(length, zeroes):
	asdf = []
	x = 0
	for i in range(zeroes - 1):
		asdf.append(True)
		asdf.append(False)
		x += 2
	for j in range(x, x + (length - x) // 2):
		asdf.append(True)
	for k in range(x + (length - x) // 2, length):
		asdf.append(False)
	return asdf

def getAns(string, l, m):
	real = []
	for char in string:
		if char == ')':
			real.append(False)
		else:
			real.append(True)
	endgoal = craftIdeal(l, m)
	operations = []
	temp = []
	for i in range(l):
		target = endgoal[i]
		if real[i] != target:
			nextDiffIndex = i + 1
			while real[nextDiffIndex] != target:
				nextDiffIndex += 1
			temp = real[i:nextDiffIndex + 1]
			for j in range(i, nextDiffIndex + 1):
				real[j] = temp[nextDiffIndex - j]
			operations.append(str(i + 1) + ' ' + str(nextDiffIndex + 1))
	print(len(operations))
	for e in operations:
		print(e)
	return
n = int(input())
for i in range(n):
	k = [int(x) for x in input().split(' ')]
	getAns(input(), k[0], k[1])


from collections import deque
for t in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	l = (n - (k - 1) * 2) // 2
	s1 = '(' * l + ')' * l + (k - 1) * '()'
	m = 0
	res = deque()
	(op, ed) = (deque(), deque())
	for i in range(n):
		if s[i] != s1[i]:
			if s[i] == '(':
				op.append(i)
			else:
				ed.append(i)
		if op and ed:
			m += 1
			left = op.pop()
			right = ed.pop()
			if left > right:
				(left, right) = (right, left)
			res.append([left + 1, right + 1])
			if right - left > 2:
				res.append([left + 1 + 1, right + 1 - 1])
				m += 1
	print(m)
	for i in range(m):
		print(*res.popleft())


def newstroka(f, a):
	pp = f
	new = []
	ss = 0
	for i in range(0, a, 2):
		if f == 0:
			ss = i
			break
		else:
			f -= 1
			new.append('(')
			new.append(')')
	if pp + 1 != a // 2 + 1:
		for i in range(ss, ss + (a - ss) // 2):
			new.append('(')
		for j in range(i + 1, a):
			new.append(')')
	return new
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	c = list(input())
	f = b - 1
	newstr = newstroka(f, a)
	ansi = 0
	ans = []
	for i in range(a):
		if c[i] != newstr[i]:
			ansi += 1
			j = i + 1
			while c[i] == c[j]:
				j += 1
			ans.append((i + 1, j + 1))
			if i == 0:
				c = c[j::-1] + c[j + 1:]
			else:
				c = c[0:i] + c[j:i - 1:-1] + c[j + 1:]
	print(ansi)
	if ansi != 0:
		for i in range(ansi):
			print(*ans[i])


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = []
	s = input()
	for j in range(len(s)):
		a.append(s[j:j + 1])
	answer = (k - 1) * '()' + (n // 2 - k + 1) * '(' + (n // 2 - k + 1) * ')'
	b = []
	for j in range(len(answer)):
		b.append(answer[j:j + 1])
	ans = []
	j = 0
	while j < len(answer):
		if b[j] == a[j]:
			j += 1
		else:
			x = j + 1
			while a[x] == a[j]:
				x += 1
			ans.append([j + 1, x + 1])
			for f in range(j, j + (x - j + 1) // 2):
				(a[f], a[x - f + j]) = (a[x - f + j], a[f])
			j += 1
	print(len(ans))
	for j in range(len(ans)):
		print(' '.join(map(str, ans[j])))


t = int(input())
for request in range(t):
	(n, k) = map(int, input().split())
	box = list(input())
	pattern = '()' * (k - 1) + '(' + '()' * ((n - k * 2) // 2) + ')'
	changes = []
	for i in range(n):
		if box[i] != pattern[i]:
			for j in range(i + 1, n):
				if box[j] == pattern[i]:
					for z in range((j - i + 1) // 2):
						(box[i + z], box[j - z]) = (box[j - z], box[i + z])
					changes.append((i + 1, j + 1))
					break
	print(len(changes))
	for i in range(len(changes)):
		print(*changes[i])


def generateTarget(n, k):
	res = []
	for _ in range(k - 1):
		res.append('()')
	remaining = n - (k - 1) * 2
	for _ in range(remaining // 2):
		res.append('(')
	for _ in range(remaining // 2):
		res.append(')')
	return ''.join(res)

def reverseInPlace(arr, i, j):
	while i < j:
		temp = arr[i]
		arr[i] = arr[j]
		arr[j] = temp
		i += 1
		j -= 1
	return

def findNext(arr, i, c):
	j = i + 1
	while arr[j] != c:
		j += 1
	return j

def main():
	t = int(input())
	allans = []
	for _ in range(t):
		(n, k) = readIntArr()
		arr = list(input())
		target = generateTarget(n, k)
		ans = []
		for i in range(n):
			if arr[i] != target[i]:
				j = findNext(arr, i, target[i])
				reverseInPlace(arr, i, j)
				ans.append([i + 1, j + 1])
		m = len(ans)
		allans.append([m])
		for x in ans:
			allans.append(x)
	multiLineArrayOfArraysPrint(allans)
	return
import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
	dv = defaultValFactory
	da = dimensionArr
	if len(da) == 1:
		return [dv() for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(i, j):
	print('? {} {}'.format(i, j))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ans):
	print('! {}'.format(' '.join([str(x) for x in ans])))
	sys.stdout.flush()
inf = float('inf')
MOD = 10 ** 9 + 7
for _abc in range(1):
	main()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	S = [i for i in input()]

	def reverse(start, end):
		while start < end:
			(S[start], S[end]) = (S[end], S[start])
			start += 1
			end -= 1
	move = 0
	pos = 0
	ans = []
	for i in range(k - 1):
		if S[pos] == '(':
			pass
		else:
			for it in range(pos, n):
				if S[it] == '(':
					reverse(pos, it)
					ans.append((pos + 1, it + 1))
					move += 1
					break
		if S[pos + 1] == ')':
			pass
		else:
			for it in range(pos + 1, n):
				if S[it] == ')':
					reverse(pos + 1, it)
					ans.append((pos + 2, it + 1))
					move += 1
					break
		pos += 2
	for i in range(int((n - (k - 1) * 2) / 2)):
		if S[pos] == '(':
			pass
		else:
			for it in range(pos, n):
				if S[it] == '(':
					reverse(pos, it)
					ans.append((pos + 1, it + 1))
					move += 1
					break
		pos += 1
	print(move)
	for i in ans:
		print(*i)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = input()
	j = 0
	ans = []
	while j < n:
		if s[j] == '(':
			q = j + 1
			while s[q] != ')':
				q += 1
			(first, second) = (j + 2, q + 1)
			if first > second:
				(first, second) = (second, first)
			if q + 1 >= n:
				p = ''
			else:
				p = s[q + 1:]
			b = s[j + 1:q + 1]
			s = s[:j + 1] + b[::-1] + p
			j += 2
		else:
			q = j + 1
			while s[q] != '(':
				q += 1
			(first, second) = (j + 1, q + 1)
			if first > second:
				(first, second) = (second, first)
			if q + 1 >= n:
				p = ''
			else:
				p = s[q + 1:]
			a = s[:j]
			b = s[j:q + 1]
			s = s[:j] + b[::-1] + p
		if first != second:
			ans.append([first, second])
	if k * 2 != n:
		ans.append([2 * k, n - 1])
	print(len(ans))
	for i in ans:
		print(i[0], i[1])


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] >= k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater

def change(s, i, j):
	d = dict()
	s = list(s)
	i -= 1
	j -= 1
	t = ''
	for k in range(i, j + 1):
		t += s[k]
	t = t[::-1]
	y = i
	for k in range(i, j + 1):
		s[k] = t[k - y]
	d.update({'(': []})
	d.update({')': []})
	for i in range(n):
		d[s[i]].append(i)
	return [d, s]
for i1 in range(int(input())):
	(n, k) = map(int, input().split())
	s = list(input())
	d = dict()
	d.update({'(': []})
	d.update({')': []})
	for i in range(n):
		d[s[i]].append(i)
	e = ''
	e = '()' * (k - 1)
	l = n - len(e)
	e += '(' * (l // 2) + ')' * (l // 2)
	l = 0
	end = 0
	ans = 0
	u = []
	e = list(e)
	for i in range(n):
		if e[i] != s[i]:
			ans += 1
			r = countGreater(d[e[i]], len(d[e[i]]), i)
			y = d[e[i]][len(d[e[i]]) - r]
			u.append([i + 1, y + 1])
			(d, s) = change(s, i + 1, y + 1)
	print(ans)
	for i in u:
		print(*i, sep=' ')


t = int(input())
for z in range(t):
	(n, k) = map(int, input().split())
	arr = list(input())
	need = '()' * (k - 1) + '(' * ((n - (k - 1) * 2) // 2) + ')' * ((n - (k - 1) * 2) // 2)
	li = 0
	ri = n - 1
	ln = 0
	rn = n - 1
	ret = []
	rev = 0
	while li < n:
		if arr[li] != need[li]:
			ri = li + 1
			while arr[ri] != need[li]:
				ri += 1
			ret.append([li, ri])
			arr = arr[:li] + list(reversed(arr[li:ri + 1])) + arr[ri + 1:]
		li += 1
	print(len(ret))
	for x in ret:
		print(x[0] + 1, x[1] + 1)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = str(input())
	sl = list(s)
	ct = 0
	d = 0
	output = []
	if sl[0] == ')':
		output.append((0, sl.index('(')))
		sl[0:sl.index('(') + 1] = reversed(sl[0:sl.index('(') + 1])
	for i in range(1, n):
		if ct == k - 1:
			d = i
			break
		if i % 2 == 1:
			for ii in range(i, n):
				if sl[ii] == ')':
					sl[i:ii + 1] = reversed(sl[i:ii + 1])
					output.append((i, ii))
					break
		if i % 2 == 0:
			for ii in range(i, n):
				if sl[ii] == '(':
					sl[i:ii + 1] = reversed(sl[i:ii + 1])
					output.append((i, ii))
					break
		if i % 2 == 0:
			ct += 1
	for i in range(d, d + (n - d) // 2):
		for ii in range(i, n):
			if sl[ii] == '(':
				sl[i:ii + 1] = reversed(sl[i:ii + 1])
				output.append((i, ii))
				break
	print(len(output))
	for i in output:
		print(i[0] + 1, i[1] + 1)


import sys as _sys

def main():
	t = int(input())
	for i_t in range(t):
		(n, k) = _read_ints()
		s = _read_line()
		operations = tuple(how_to_make_room_clean(s, k))
		print(len(operations))
		for (l, r) in operations:
			print(l + 1, r + 1)

def _read_line():
	result = _sys.stdin.readline()
	assert result[-1] == '\n'
	return result[:-1]

def _read_ints():
	return map(int, _read_line().split())

def how_to_make_room_clean(s, k):
	n = len(s)
	assert n % 2 == 0
	assert s.count('(') == s.count(')')

	def apply(l, r):
		nonlocal s
		s = s[:l] + s[l:r + 1][::-1] + s[r + 1:]
	how_many_perfect_need = 2 * (k - 1)
	i_first_not_perfect = 0
	while True:
		while i_first_not_perfect < how_many_perfect_need and s[i_first_not_perfect:i_first_not_perfect + 2] == '()':
			i_first_not_perfect += 2
		if i_first_not_perfect >= how_many_perfect_need:
			break
		if ')(' not in s[i_first_not_perfect:]:
			r = s.index('()', i_first_not_perfect) + 1
			yield (i_first_not_perfect, r)
			apply(i_first_not_perfect, r)
		r = s.index(')(', i_first_not_perfect) + 1
		yield (i_first_not_perfect, r)
		apply(i_first_not_perfect, r)
	i_first_not_opening = how_many_perfect_need
	first_not_opening_stop = i_first_not_opening + (n - how_many_perfect_need) // 2
	while True:
		while i_first_not_opening < first_not_opening_stop and s[i_first_not_opening] == '(':
			i_first_not_opening += 1
		if i_first_not_opening >= first_not_opening_stop:
			break
		r = s.index('(', i_first_not_opening)
		yield (i_first_not_opening, r)
		apply(i_first_not_opening, r)
main()


m = int(input())
for h in range(m):
	(n, b) = map(int, input().split())
	a = input()
	t = 0
	ans = []
	while b != 1:
		if a[t] == ')':
			for i in range(t, n):
				if a[i] == '(':
					k = i
					break
			c = a[t:k + 1]
			a = a[:t] + c[::-1] + a[k + 1:]
			ans.append([t, k])
		if a[t + 1] == '(':
			for i in range(t + 1, n):
				if a[i] == ')':
					k = i
					break
			c = a[t + 1:k + 1]
			a = a[:t + 1] + c[::-1] + a[k + 1:]
			ans.append([t + 1, k])
		t += 2
		b -= 1
	for i in range(t, t + (n - t) // 2):
		if a[i] == ')':
			for j in range(i, n):
				if a[j] == '(':
					k = j
					break
			c = a[i:k + 1]
			a = a[:i] + c[::-1] + a[k + 1:]
			ans.append([i, k])
	for i in range(t + (n - t) // 2, n):
		if a[i] == '(':
			for j in range(i, n):
				if a[j] == ')':
					k = j
					break
			c = a[i:k + 1]
			a = a[:i] + c[::-1] + a[k + 1:]
			ans.append([i, k])
	print(len(ans))
	for i in ans:
		print(i[0] + 1, i[1] + 1)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	(*s,) = input()
	operations = []
	best = (['('] + [')']) * (k - 1) + (['('] * (n // 2 - k + 1) + [')'] * (n // 2 - k + 1))
	for startx_pos in range((k - 1) * 2):
		try:
			if s[startx_pos - 1] == ')' or startx_pos == 0:
				end_pos = s.index('(', startx_pos)
			else:
				end_pos = s.index(')', startx_pos)
		except ValueError:
			continue
		if startx_pos == end_pos:
			continue
		if startx_pos == 0:
			s = s[:startx_pos] + s[end_pos::-1] + s[end_pos + 1:]
		else:
			s = s[:startx_pos] + s[end_pos:startx_pos - 1:-1] + s[end_pos + 1:]
		operations.append(f'{startx_pos + 1} {end_pos + 1}')
	for startx_pos in range((k - 1) * 2, (k - 1) * 2 + (n // 2 - k + 1)):
		try:
			end_pos = s.index('(', startx_pos)
		except ValueError:
			continue
		if startx_pos == end_pos:
			continue
		if startx_pos == 0:
			s = s[:startx_pos] + s[end_pos::-1] + s[end_pos + 1:]
		else:
			s = s[:startx_pos] + s[end_pos:startx_pos - 1:-1] + s[end_pos + 1:]
		operations.append(f'{startx_pos + 1} {end_pos + 1}')
	print(len(operations))
	if len(operations):
		print(*operations, sep='\n')


def replace(i, right_s):
	j = i + 1
	while j < n and s[j] != right_s:
		j += 1
	else:
		for k in range((j - i + 1) // 2):
			(s[i + k], s[j - k]) = (s[j - k], s[i + k])
	return j
t = int(input())
operations = []
for _ in range(t):
	(n, k) = input().split()
	n = int(n)
	k = int(k) - 1
	s = list(input())
	operations.append([])
	for i in range(n):
		if i < 2 * k:
			if i % 2 and s[i] == '(':
				operations[_].append([i, replace(i, ')')])
			elif i % 2 == 0 and s[i] == ')':
				operations[_].append([i, replace(i, '(')])
		elif i < n // 2 + k and s[i] == ')':
			operations[_].append([i, replace(i, '(')])
		elif i >= n // 2 + k and s[i] == '(':
			operations[_].append([i, replace(i, ')')])
for i in range(t):
	print(len(operations[i]))
	for operation in operations[i]:
		print(operation[0] + 1, operation[1] + 1)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	a = input()
	k -= 1
	t = k
	h = n - 2 * t
	c = '(' * (h // 2) + ')' * (h // 2) + '()' * t
	b = []
	for i in range(n):
		if c[i] != a[i]:
			q = c[i]
			for j in range(i + 1, n):
				if q == a[j]:
					b.append([i + 1, j + 1])
					s = a[i:j + 1]
					a = a[:i] + s[::-1] + a[j + 1:]
					break
	print(len(b))
	for x in b:
		print(*x)


kT = int(input())
ans = []
for iter in range(kT):
	ans.append([])
	(n, k) = map(int, input().split())
	s = list(input())
	l = 0
	while k != 1:
		r = l
		while s[r] != '(':
			r += 1
		s = s[:l] + s[l:r + 1][::-1] + s[r + 1:]
		ans[iter].append([l + 1, r + 1])
		l += 1
		r = l
		while s[r] != ')':
			r += 1
		s = s[:l] + s[l:r + 1][::-1] + s[r + 1:]
		ans[iter].append([l + 1, r + 1])
		k -= 1
		l += 1
	xxx = (len(s) - l) // 2
	a = 0
	while a < xxx:
		r = l
		while s[r] != '(':
			r += 1
		s = s[:l] + s[l:r + 1][::-1] + s[r + 1:]
		ans[iter].append([l + 1, r + 1])
		l += 1
		a += 1
	a = 0
	while a < xxx:
		r = l
		while s[r] != ')':
			r += 1
		s = s[:l] + s[l:r + 1][::-1] + s[r + 1:]
		ans[iter].append([l + 1, r + 1])
		k -= 1
		l += 1
		a += 1
for i in range(kT):
	print(len(ans[i]))
	for j in range(len(ans[i])):
		print(*ans[i][j])


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	s = input()
	s = [s[i] for i in range(n)]
	limit = (k - 1) * 2
	l = 0
	answer = []
	answerk = 0
	for r in range(n):
		if s[r] == '(':
			if l != r:
				answer.append([l + 1, r + 1])
				answerk += 1
			l += 1
	l = 1
	r = n // 2
	for j in range(k - 1):
		answer.append([l + 1, r + 1])
		answerk += 1
		l += 2
		r += 1
	print(answerk)
	[print(*i) for i in answer]