该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

探索者的银凇止境/密文板研究

终于考完 NOI 的 Displace_ 开始打集。

众所周知，密文板分为布局和本因两种，宣告时只能将相同颜色的本因和布局合并起来，并且合并后两个密文板都将消失（这里不考虑密文板的修辞）。

密文板宣告带来的增益是十分强大的，所以 Displace_ 想要尽量多的合并密文板。

题目描述

因为 Displace_ 的勘察设备是专业改装，所以他已经预知了密文板按照获得时间排成的序列。具体的，抽象成了一个括号序列，用 ( 表示本因，) 表示布局。

因为他的强迫症，每个布局只能和获得时间早于它的本因合并。

因为有不期而遇节点的存在，所以有一些时刻获得的密文板无法知道具体是什么，我们认为该密文板在本因和布局中等概率获得，用 ? 表示。

Displace_ 会把所有能合并的密文板都合并掉，直到剩下的密文板找不到任何能合并的一对。

Displace_ 想知道最好情况下能剩下最少的密文板的数量，请你构造出一个可能的方案。

因为密文板的颜色有很多，所以你需要回答多组数据。

输入格式

第一行一个整数 $T$ ，表示数据组数。

接下来一共 $T$ 组数据。

对于每组数据，第一行一个整数 $n$，表示字符串长度；接下来一行一个字符串，保证只包含 (、) 和 ? 。

输出格式

一共输出 $T$ 组答案，每组第一行一个整数表示最少的数量，第二行一个字符串表示你构造的方案，任意一种合法的方案都是可以的。

样例输入

1
5
?(?)(

样例输出

1
(())(

数据范围与时空限制

1s，512MB

对于所有测试点，保证 $T\leq 5，n\leq 100000$，字符串只由 (、) 和 ?。

测试点编号	$n\leq$
1	20
2
3	100
4
5	1000
6
7
8	100000
9
10