#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1000005;
const ll mod=998244353;
inline int rd()
{
	int x=0; bool f=1;
	char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar())
		if(ch=='-') f=0;
	for(;ch>='0'&&ch<='9';ch=getchar())
		x=x*10+(ch^48);
	return f?x:-x;
}
#define ck(x) ((x)=='('||(x)==')')
char s[N];
int stk[N],tp;
int lst[N];
bool solve(int l,int r)
{
	int m=(r-l+1)/2-1;
	for(int i=l;i<=l+m;i++)
		if(ck(s[i])!=ck(s[r-i+l]))
			return 0;
	for(int i=l+1;i<=l+m;i++)
		if(ck(s[i])==ck(s[i-1]))
			return 0;
	return 1;
}
bool vis[2];
int main()
{
	int t=rd();
	while(t--)
	{
		vis[0]=vis[1]=0;
		scanf("%s",s+1);
		int n=strlen(s+1);
		for(int i=1;i<=n;i++)
		{
			if(tp&&ck(s[stk[tp]])==ck(s[i]))
				lst[stk[tp]]=i,tp--,s[i]=(ck(s[i])?')':']');
			else
				stk[++tp]=i,s[i]=(ck(s[i])?'(':'[');
		}
		if(tp)
		{
			printf("No\n");
			continue;
		}
		bool bb=1;
		int l=1,r;
		while(l<=n)
		{
			r=lst[l];
			bb&=solve(l,r);
			if(vis[ck(l)]) bb=0;
			vis[ck(l)]=1;
			l=r+1;
		}
		if(bb)
			printf("Yes\n");
		else
			printf("No\n");
	}
	return 0;
}