A 密文板
我们考虑两个栈，一个维护左括号，一个维护问号；
如果来了一个右括号，优先使用左括号，然后使用问号；
多余的问号，与左括号匹配；
最后再多余，问号自己互相匹配。
#include<iostream>
#include<cstring>
using namespace std;
#define Ed for(int i=h[x];~i;i=ne[i])
#define Ls(i,l,r) for(int i=l;i<r;++i)
#define Rs(i,l,r) for(int i=l;i>r;--i)
#define Le(i,l,r) for(int i=l;i<=r;++i)
#define Re(i,l,r) for(int i=l;i>=r;--i)
#define L(i,l) for(int i=0;i<l;++i)
#define E(i,l) for(int i=1;i<=l;++i)
#define W(t) while(t--)
#define Wh while
const int N=100010;
int T,n,tp1,stk1[N],tp2,stk2[N];
char s[N];
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>T;
W(T){
tp1=tp2=0;
int ans=0;
cin>>n>>s;
L(i, n){
if(s[i]=='(')stk1[++tp1]=i;
else if(s[i]==')'){
if(tp1)--tp1;
else if(tp2){
s[stk2[tp2--]]='(';
}
else ++ans;
}
else stk2[++tp2]=i;
}
Wh(tp1){
if(tp2&&stk2[tp2]>stk1[tp1]){
s[stk2[tp2--]]=')';
tp1--;
}
else tp1--,++ans;
}
if(tp2&1)++ans;
E(i, tp2)
if(i&1)s[stk2[i]]='(';
else s[stk2[i]]=')';
cout<<ans<<'\n'<<s<<'\n';
}
return 0;
}