Problem: A bracket sequence is called regular if it is possible to obtain correct arithmetic expression by inserting characters + and 1 into this sequence. For example, sequences (())(), () and (()(())) are regular, while )(, (() and (()))( are not. Let's call a regular bracket sequence "RBS".

You are given a sequence s of n characters (, ), and/or ?. There is exactly one character ( and exactly one character ) in this sequence.

You have to replace every character ? with either ) or ( (different characters ? can be replaced with different brackets). You cannot reorder the characters, remove them, insert other characters, and each ? must be replaced.

Determine if it is possible to obtain an RBS after these replacements.

Input

The first line contains one integer t (1 ≤ t ≤ 1000) — the number of test cases.

Each test case consists of one line containing s (2 ≤ |s| ≤ 100) — a sequence of characters (, ), and/or ?. There is exactly one character ( and exactly one character ) in this sequence.

Output

For each test case, print YES if it is possible to obtain a regular bracket sequence, or NO otherwise}. 

You may print each letter in any case (for example, YES, Yes, yes, yEs will all be recognized as positive answer).

Example

Input


5
()
(?)
(??)
??()
)?(?


Output


YES
NO
YES
YES
NO

Note

In the first test case, the sequence is already an RBS.

In the third test case, you can obtain an RBS as follows: ()() or (()).

In the fourth test case, you can obtain an RBS as follows: ()().

Solution (in JAVA):

Solution:
import java.io.BufferedInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Random;

public class Problem {
	public static void main(String[] args) throws Exception {
		Erickde scan = new Erickde();
		PrintWriter out = new PrintWriter(System.out);
		int t = scan.nextInt();
		while (t-- > 0) {
			String s = scan.next();
			int counte = 0;
			int counto = 0;
			int countq = 0;
			if (s.charAt(0) == ')' || s.charAt(s.length() - 1) == '(') {
				System.out.println("NO");
			} else {
				for (int i = 0; i < s.length(); i++) {
					if (s.charAt(i) == '(') {
						counte++;
					} else if (s.charAt(i) == ')') {
						counto++;
					} else {
						countq++;
					}
				}
				if (counte == counto && countq % 2 == 0) {
					System.out.println("YES");
				} else if (counte == countq && counto == 0 || counto == countq && counte == 0) {
					System.out.println("YES");
				} else {
					System.out.println("NO");
				}
			}
		}
	}

	public static void moveZeroes(int[] nums) {
		int count = 0;
		for (int i = 0; i < nums.length; i++) {
			if (nums[i] == 0) {
				count++;
			}

		}
		while (count-- > 0) {
			for (int j = 0; j < nums.length - 1; j++) {
				if (nums[j] == 0) {
					int temp = nums[j];
					nums[j] = nums[j + 1];
					nums[j + 1] = temp;

				}
			}
		}
	}

	public static int[] twoSum(int[] nums, int target) {
		HashMap<Integer, Integer> sum = new HashMap<>();
		for (int i = 0; i < nums.length; i++) {
			int key = target - nums[i];
			if (sum.containsKey(key)) {
				return new int[] { sum.get(key), i };
			}
			sum.put(nums[i], i);
		}
		throw new IllegalArgumentException("Not found");

	}

	public boolean isValidSudoku(char[][] board) {
		HashSet seen = new HashSet();
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < board.length; j++) {
				char num = board[i][j];
				if (num != '.') {
					if ((!seen.add(num + "in row" + i)) || (!seen.add(num + "in col" + j))
							|| ((!seen.add(num + "in block" + i / 3 + "-" + j / 3)))) {
						return false;
					}
				}

			}
		}
		return true;

	}

	public void rotate(int[][] matrix) {
		int n = matrix.length;
		for (int i = 0; i < matrix.length; i++) {
			for (int j = i; j < n; j++) {
				int temp = matrix[i][j];
				matrix[i][j] = matrix[j][i];
				matrix[j][i] = temp;
			}
		}
		for (int i = 0; i < matrix.length; i++) {
			for (int j = 0; j < matrix.length / 2; j++) {
				int temp = matrix[i][j];
				matrix[i][j] = matrix[i][n - 1 - j];
				matrix[i][n - 1 - j] = temp;
			}
		}
	}

	public void reverseString(char[] s) {
		for (int i = 0; i < s.length / 2; i++) {
			char temp = s[i];
			s[i] = s[s.length - 1 - i];
			s[s.length - 1 - i] = temp;
		}
	}

	public int reverse(int x) {

		return x;

	}

	public int[] plusOne(int[] digits) {
		int s = digits.length;
		for (int i = s - 1; s > 0; i--) {
			if (digits[i] < 9) {
				digits[i]++;
				return digits;
			}
			digits[i] = 0;

		}
		int arr[] = new int[s + 1];
		arr[0] = 1;
		return arr;
	}

	static class Erickde {
		private int BS = 1 << 16;

		private char NC = (char) 0;
		private byte[] buf = new byte[BS];
		private int bId = 0, size = 0;
		private char c = NC;
		private double cnt = 1;
		private BufferedInputStream in;

		public Erickde() {
			in = new BufferedInputStream(System.in, BS);
		}

		public Erickde(String s) {
			try {
				in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
			} catch (Exception e) {
				in = new BufferedInputStream(System.in, BS);
			}
		}

		private char getChar() {
			while (bId == size) {
				try {
					size = in.read(buf);
				} catch (Exception e) {
					return NC;
				}
				if (size == -1)
					return NC;
				bId = 0;
			}
			return (char) buf[bId++];
		}

		public int nextInt() {
			return (int) nextLong();
		}

		public int[] nextInts(int N) {
			int[] res = new int[N];
			for (int i = 0; i < N; i++) {
				res[i] = (int) nextLong();
			}
			return res;
		}

		public long[] nextLongs(int N) {
			long[] res = new long[N];
			for (int i = 0; i < N; i++) {
				res[i] = nextLong();
			}
			return res;
		}

		public long nextLong() {
			cnt = 1;
			boolean neg = false;
			if (c == NC)
				c = getChar();
			for (; (c < '0' || c > '9'); c = getChar()) {
				if (c == '-')
					neg = true;
			}
			long res = 0;
			for (; c >= '0' && c <= '9'; c = getChar()) {
				res = (res << 3) + (res << 1) + c - '0';
				cnt *= 10;
			}
			return neg ? -res : res;
		}

		public double nextDouble() {
			double cur = nextLong();
			return c != '.' ? cur : cur + nextLong() / cnt;
		}

		public String next() {
			StringBuilder res = new StringBuilder();
			while (c <= 32)
				c = getChar();
			while (c > 32) {
				res.append(c);
				c = getChar();
			}
			return res.toString();
		}

		public String nextLine() {
			StringBuilder res = new StringBuilder();
			while (c <= 32)
				c = getChar();
			while (c != '\n') {
				res.append(c);
				c = getChar();
			}
			return res.toString();
		}

		public boolean hasNext() {
			if (c > 32)
				return true;
			while (true) {
				c = getChar();
				if (c == NC)
					return false;
				else if (c > 32)
					return true;
			}
		}
	}

	public static void quicksort(int[] a) {
		if (a == null)
			return;
		quicksort(a, 0, a.length - 1);
	}

	private static void quicksort(int[] a, int lo, int hi) {
		if (lo < hi) {
			int splitPoint = partition(a, lo, hi);
			quicksort(a, lo, splitPoint);
			quicksort(a, splitPoint + 1, hi);
		}
	}

	private static final double EPS = 0.00000001;

	private static int partition(int[] a, int lo, int hi) {
		int pivot = a[lo];
		int i = lo - 1, j = hi + 1;
		while (true) {
			do {
				i++;
			} while (a[i] < pivot);
			do {
				j--;
			} while (a[j] > pivot);
			if (i < j)
				swap(a, i, j);
			else
				return j;
		}
	}

	private static void swap(int[] ar, int i, int j) {
		int tmp = ar[i];
		ar[i] = ar[j];
		ar[j] = tmp;
	}

	static Random RANDOM = new Random();

	static int randInt(int min, int max) {
		return RANDOM.nextInt((max - min) + 1) + min;
	}

	public static int findMaxGCD(int arr[], int n) {

		int high = 0;
		for (int i = 0; i < n; i++)
			high = Math.max(high, arr[i]);

		int divisors[] = new int[high + 1];

		for (int i = 0; i < n; i++) {

			for (int j = 1; j <= Math.sqrt(arr[i]); j++) {

				if (arr[i] % j == 0) {

					divisors[j]++;

					if (j != arr[i] / j)
						divisors[arr[i] / j]++;
				}
			}
		}

		for (int i = high; i >= 1; i--)

			if (divisors[i] > 1)
				return i;
		return 1;
	}

	static int arraySortedOrNot(int arr[], int n) {

		if (n == 1 || n == 0)
			return 1;

		if (arr[n - 1] < arr[n - 2])
			return 0;

		return arraySortedOrNot(arr, n - 1);
	}

	static boolean isPrime(int n) {

		if (n <= 1)
			return false;

		else if (n == 2)
			return true;

		else if (n % 2 == 0)
			return false;

		for (int i = 3; i <= Math.sqrt(n); i += 2) {
			if (n % i == 0)
				return false;
		}
		return true;
	}

	public int removeDuplicates(int[] nums) {
		if (nums.length < 2) {
			return nums.length;
		}
		int i = 1;
		int j = 0;
		while (i < nums.length) {
			if (nums[i] != nums[j]) {
				j++;
				nums[j] = nums[i];
			}
			i++;
		}
		return j + 1;
	}

	public static boolean containsDuplicate(int[] nums) {
		HashSet<Integer> numbers = new HashSet<>();
		for (int i = 0; i < nums.length; i++) {
			if (numbers.contains(nums[i])) {
				return true;
			} else {
				numbers.add(nums[i]);
			}
		}
		return false;

	}

	public int singleNumber(int[] nums) {
		int res = 0;
		for (int i = 0; i < nums.length; i++) {
			res ^= nums[i];
		}
		return res;

	}

}