t = int(input())
for i in range(t):
    s = input()
    if len(s) % 2 == 0 and s[0] != ')' and s[-1] != '(':
        print('YES')
    else:
        print('NO')

t = int(input())
for i in range(t):
    s = input()
    n = len(s)
    a = [s[i] for i in range(n)]
    cnt = n // 2 - 1
    for j in range(n):
        if a[j] == '?':
            if cnt > 0:
                cnt -= 1
                a[j] = '('
            else:
                a[j] = ')'
    bal = 0
    minbal = 0
    for j in range(n):
        if a[j] == '(':
            bal += 1
        else:
            bal -= 1
        minbal = min(bal, minbal)
    print('YES' if bal == 0 and minbal >= 0 else 'NO') 

#include <bits/stdc++.h>

using namespace std;

void solve() {
	int n;
	cin >> n;
	vector<int> r(n);
	for (int &x : r) cin >> x;
	int m;
	cin >> m;
	vector<int> b(m);
	for (int &x : b) cin >> x;
	partial_sum(r.begin(), r.end(), r.begin());
	partial_sum(b.begin(), b.end(), b.begin());
	cout << max(0, *max_element(r.begin(), r.end())) + max(0, *max_element(b.begin(), b.end())) << '\n';
}

int main() {
	int t;
	cin >> t;
	while (t--) solve();
}

for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	m = int(input())
	b = [int(x) for x in input().split()]
	dp = [[-10**9 for j in range(m + 1)] for i in range(n + 1)]
	dp[0][0] = 0
	ans = 0
	for i in range(n + 1):
		for j in range(m + 1):
			if i < n:
				dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + a[i])
			if j < m:
				dp[i][j + 1] = max(dp[i][j + 1], dp[i][j] + b[j])
			ans = max(ans, dp[i][j])
	print(ans)

fun main() {
    repeat(readLine()!!.toInt()) {
        val (n, k) = readLine()!!.split(' ').map { it.toInt() }
        val h = readLine()!!.split(' ').map { it.toInt() }

        var mn = h[0]
        var mx = h[0]
        var ok = true
        for (i in 1 until n) {
            mn = maxOf(mn - k + 1, h[i])
            mx = minOf(mx + k - 1, h[i] + k - 1)
            if (mn > mx) {
                ok = false
                break
            }
        }
        if (h[n - 1] !in mn..mx)
            ok = false
        println(if (ok) "YES" else "NO")
    }
}

#include<bits/stdc++.h>

using namespace std;

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())

#define x first
#define y second

typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;

const int INF = int(1e9);
const li INF64 = li(1e18);
const ld EPS = 1e-9;

int n;

inline bool read() {
	if(!(cin >> n))
		return false;
	return true;
}

void calc(int n, vector<pt> &ans) {
	if (n == 2)
		return;
	
	int y = max(1, (int)sqrt(n) - 1);
	while (y < (n + y - 1) / y)
		y++;
	
	fore (pos, y + 1, n)
		ans.emplace_back(pos, n);
	ans.emplace_back(n, y);
	ans.emplace_back(n, y);
	
	calc(y, ans);
}

inline void solve() {
	vector<pt> ans;
	calc(n, ans);
	
	cout << sz(ans) << endl;
	for(auto p : ans)
		cout << p.first << " " << p.second << '\n';
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	int tt = clock();
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cout << fixed << setprecision(15);
	
	int tc; cin >> tc;
	while(tc--) {
		read();
		solve();
		
#ifdef _DEBUG
		cerr << "TIME = " << clock() - tt << endl;
		tt = clock();
#endif
	}
	return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int N = 1000043;                 
int q;
char buf[N];
int n, k;

int ceilLog(int x)
{
    int y = 0;
    while((1 << y) < x)
        y++;
    return y;
}

int main()
{
    scanf("%d", &q);
    for(int i = 0; i < q; i++)
    {
        scanf("%d %d", &n, &k);
        scanf("%s", buf);
        string s = buf;
        int m = min(k, ceilLog(n - k + 2));
        vector<int> used(1 << m, 0);
        vector<int> next0(n, int(1e9));
        if(s[n - 1] == '0')
            next0[n - 1] = n - 1;
        for(int j = n - 2; j >= 0; j--)
            if(s[j] == '0')
                next0[j] = j;
            else
                next0[j] = next0[j + 1];
        int d = k - m;
        for(int j = 0; j < n - k + 1; j++)
        {
            if(next0[j] - j < d)
                continue;
            int cur = 0;
            for(int x = j + d; x < j + k; x++)
                cur = cur * 2 + (s[x] - '0');
            used[((1 << m) - 1) ^ cur] = 1;    
        }
        int ans = -1;
        for(int j = 0; j < (1 << m); j++)
            if(used[j] == 0)
            {
                ans = j;
                break;    
            }
        if(ans == -1)
            puts("NO");
        else
        {
            puts("YES");
            string res(d, '0');
            string res2;
            for(int j = 0; j < m; j++)
            {
                res2.push_back('0' + (ans % 2));
                ans /= 2;
            }
            reverse(res2.begin(), res2.end());
            res += res2;
            puts(res.c_str());
        }
    }
}

#include <bits/stdc++.h>

#define forn(i, n) for (int i = 0; i < int(n); i++)

using namespace std;

const int INF = 1e9;

int n, k, nn;

vector<long long> t, ps;

void push(int v, int l, int r){
	if (l < r - 1){
		ps[v * 2] += ps[v];
		ps[v * 2 + 1] += ps[v];
	}
	t[v] += ps[v] * (r - l);
	ps[v] = 0;
}

void upd(int v, int l, int r, int L, int R, int val){
	push(v, l, r);
	if (L >= R)
		return;
	if (l == L && r == R){
		ps[v] = val;
		push(v, l, r);
		return;
	}
	int m = (l + r) / 2;
	upd(v * 2, l, m, L, min(m, R), val);
	upd(v * 2 + 1, m, r, max(m, L), R, val);
	t[v] = t[v * 2] + t[v * 2 + 1];
}

long long get(int v, int l, int r, int L, int R){
	push(v, l, r);
	if (L >= R)
		return 0;
	if (l == L && r == R)
		return t[v];
	int m = (l + r) / 2;
	long long res = get(v * 2, l, m, L, min(m, R)) + get(v * 2 + 1, m, r, max(m, L), R);
	t[v] = t[v * 2] + t[v * 2 + 1];
	return res;
}

int trav(int v, int l, int r, int cnt){
	push(v, l, r);
	if (l == r - 1)
		return l;
	int m = (l + r) / 2;
	push(v * 2, l, m);
	push(v * 2 + 1, m, r);
	int res = INF;
	if (t[v * 2] >= cnt)
		res = trav(v * 2, l, m, cnt);
	else if (t[v * 2 + 1] >= cnt - t[v * 2])
		res = trav(v * 2 + 1, m, r, cnt - t[v * 2]);
	t[v] = t[v * 2] + t[v * 2 + 1];
	return res;
}

int main() {
	scanf("%d%d", &n, &k);
	vector<int> a(n);
	forn(i, n) scanf("%d", &a[i]);
	sort(a.begin(), a.end(), greater<int>());
	nn = a[0] + 500;
	t.resize(4 * nn);
	ps.resize(4 * nn);
	upd(1, 0, nn, 0, 1, 1);
	int fst = 0;
	int ans = INF;
	forn(i, n){
		while (get(1, 0, nn, 0, fst + 1) == 0) ++fst;
		upd(1, 0, nn, fst, fst + 1, -1);
		upd(1, 0, nn, fst + 2, fst + 2 + (a[i] - 1) / 2, 1);
		upd(1, 0, nn, fst + 2, fst + 2 + a[i] / 2, 1);
		ans = min(ans, trav(1, 0, nn, k));
	}
	printf("%d\n", ans == INF ? -1 : ans);
	return 0;
}