For a better world

import sys

input = sys.stdin.readline
N = int(input())

for _ in range(N):
    ps = input()
    _sum = 0

    for i in ps:
        if i == "(":
            _sum +=1
        elif i == ")":
            _sum -=1
        
        if _sum < 0:
            break
    
    if _sum == 0:
        print ("YES")

    else:
        print ("NO")

#include <iostream>
#include <string>

using namespace std;

int main(void)
{
	
	int C = 0; // Test case
	int Sum = 0;
	int Weight = 0;
	string S;
	
	cin >> C;
	
	for (int i=0; i<C; i++)
	{
		cin >> S;
		if (S.length()>0 and S.length()<80)
		{
			for (int j=0; j<S.length(); j++)
			{
				if (S[j] == 'O')
				{
					Weight = Weight + 1;
					Sum = Sum + Weight;
				}
				else
					Weight = 0;
			}
			
			cout << Sum << endl;
			Sum = 0;
			Weight = 0;
		}
		

	}

	return 0;
}

#include <stdio.h>

int main(void)

{
	int n = 0;
	int sum = 0;
	
	scanf("%d", &n);
	
	if (n>=1 and n<=10000)
	{
		for (int i=1; i<=n; i++)
		{
			sum = sum + i;
		}
		printf("%d", sum);
	}
	
	return 0;
}

# -*- coding:utf-8 -*-
from collections import deque

def bfs() -> list:
    while queue:
        x, y = queue.popleft()

        for i in range(4):
            a = x + dx[i]
            b = y + dy[i]

            if 0<=a<N and 0<=b<M and graph[a][b] == 0:
                queue.append([a, b]) # 방문하지 않은 다음 노드를 큐에 삽입
                graph[a][b] = graph[x][y] + 1

    return graph

if __name__ == "__main__":

    # 초기 변수 선언 & 그래프 생성
    M, N = list(map(int, input().split()))
    graph = []
    queue = deque()

    dx = [-1, 0, 1, 0] # 익은 토마토 좌표 기준으로 사방향 드로잉을 위한 x좌표
    dy = [0, -1, 0, 1] # 익은 토마토 좌표 기준으로 사방향 드로잉을 위한 y좌표

    for i in range(N):
        graph.append(list(map(int,input().split())))

    # 익은 토마토 좌표 추출 -> 큐 삽입

    for i in range(N):
        for j in range(M):
            if graph[i][j] == 1:
                queue.append([i, j])
    
    # 토마토 숙성
    graph = bfs()

    # 결과 출력
    day = 0
    for i in graph:
        for j in i:
            if j == 0:
                print (-1)
                exit(0)
        day = max(day, max(i))
    
    print (day-1)

# -*- coding:utf-8 -*-
import sys
from collections import deque

def breadth_first_seach() -> list:
    while queue:
        z, x, y = queue.popleft()

        for i in range(6):
            a = z + dz[i]
            b = x  +dx[i]
            c = y + dy[i]

            if 0<=a<H and 0<=b<N and 0<=c<M and graph[a][b][c] == 0:
                queue.append([a, b, c])
                graph[a][b][c] = graph[z][x][y] + 1

    return graph


if __name__ == "__main__":

    # N = 행, M = 열, H = 높이
    M, N, H = list(map(int, sys.stdin.readline().split()))
    queue = deque()
    graph = [[[0 for i in range(M)] for j in range(N)] for k in range(H)]

    dx = [-1, 1, 0, 0, 0, 0]
    dy = [0, 0, 1, -1, 0, 0]
    dz = [0, 0, 0, 0, 1, -1]

    for z in range(H):
        for x in range(N): # 행
            graph[z][x] = list(map(int, sys.stdin.readline().split()))
            for y in range(M): # 열
                if graph[z][x][y] == 1:
                    queue.append([z, x, y])

    graph = breadth_first_seach()    
    
    day = 0
    for i in graph:
        for j in i:
            for k in j:
                if k == 0:
                    print (-1)
                    exit(0)
            day = max(day, max(j))
    print (day-1)

import sys

input = sys.stdin.readline
N = int(input())
students :list = [] 

for _ in range(N):
    weight, height = list(map(int, input().split()))
    students.append((weight, height))

for i in students:
    rank = 1
    for j in students:
        if i[0] < j[0] and i[1] < j[1]:
            rank +=1
    
    print (rank, end = " ")

print (124)
print ("roytravel")

import sys
from itertools import combinations

def dfs(start):
    if len(picked) == 6:
        print (*picked)
        return

    for i in range(start, len(test_case)):
        picked.append(test_case[i])
        dfs(i+1)
        picked.pop()

if __name__ == "__main__":
    # 1. manual dfs algorithm for combination
    input = sys.stdin.readline

    while True:
        test_case = list(map(int, input().split()))
        if len(test_case) == 1:
            break

        del test_case[0]
        picked = []
        dfs(0)
        print()

    # 2. using library for combination algorithm
    # while True:
    #     test_case = list(map(int, input().split()))
    #     del test_case[0]

    #     combination = combinations(test_case, 6)
    #     for element in combination:
    #         print (*element)

    #     print ()

    #     if not test_case:
    #         break

import sys
input = sys.stdin.readline

word = input()
dial = {1: "", 2:"ABC", 3:"DEF", 4:"GHI", 5:"JKL", 6:"MNO", 7:"PQRS", 8:"TUV", 9:"WXYZ", 0:""}
time = 0
for i in word:
    for key, value in dial.items():    
        if i in value:
            time += key + 1
print (time)

price = int(input())
coins = [500, 100, 50, 10, 5, 1]
change = (1000 - price)
count = 0
for coin in coins:
    Q, R = divmod(change, coin)
    count = count + Q
    change = R
    if R == 0:
        break
print (count)

#include <iostream>

#define N 10001
using namespace std;

int solution(int n)
{
	int sum = n;
	
	while(true)
	{
		if (n==0)
			break;
		
		sum = sum + (n % 10); // get the remainder
		n = n / 10; // divide by 10 to get next remainder;
	}
	
	return sum;
}


int main(void)
{
	bool Array[N] = {0, };
	int idx = 0;
	
	for (int i=1; i<N; i++)
	{
		idx = solution(i);
		
		if (idx <= N) // Why always idx is smaller or equal than N?
			Array[idx] = 1; // constructor = 1
	}
	
	for (int j=1; j<N; j++)
	{
		if (!Array[j])
			cout << j << endl;
	}
	
	return 0;
}

#include <iostream>
#include <math.h>
using namespace std;

int main(void)
{
	int C = 0;
	int N = 0;
	
	cin >> C;
	
	for (int i=0; i<C; i++) // This loop means the number of test case.
	{
		cin >> N;
		
		if (N>=1 and N<=1000)
		{
			int Sum = 0;
			double Mean = 0;
			double count = 0;
			double percent = 0;
			
			int Score[N] = {0, };
			
			for (int j=0; j<N; j++) // This loop gets the summation of input values
			{
				cin >> Score[j];
				if (Score[j]< 0 or Score[j]>100)
					return 0;
					
				Sum = Sum + Score[j];
			}
			
			Mean = Sum / N;
			
			for (int k=0; k<N; k++) // This loop gets count of people who has higher value than mean
			{
				if (Score[k] > Mean)
				{
					count = count + 1;
				}
			}
			
			percent = (count/N) * 100;
			cout << fixed;
			cout.precision(3);
			cout << round(percent * 1000) / 1000 << "%" << endl;
		}
	}
	return 0;
}

for _ in range(30000):
    length = list(map(int, input().split()))
    length = sorted(length, reverse=True)

    if pow(length[0], 2) == 0 and length[1] == 0 and length[2] == 0:
        break

    if pow(length[0], 2) == pow(length[1], 2) + pow(length[2], 2):
        print ("right")
    else:
        print ("wrong")

import sys
import math
input = sys.stdin.readline
R = int(input())
print (round(math.pi * pow(R, 2), 6))
print (round(R * R * 2, 6))

#include <iostream>
using namespace std;

int solution1()
{
	int array[10] = {0, };
	int remainder[42] = {0,};
	int count = 0;
	
	for (int i=0; i<10; i++)
	{
		cin >> array[i];
		
		if (array[i] < 0 or array[i] > 1000)
			return 0;
		
		if (!remainder[array[i] % 42]++)	
			count = count + 1;
	}
	return count;
}



int main(void)
{
	int count = 0;
	count = solution1();
	cout << count << endl;
	
	return 0;
}

import sys
from collections import Counter
input = sys.stdin.readline

def get_square_coordinate(coordinates):
    X, Y = [], []
    for xy in coordinates:
        X.append(xy[0])
        Y.append(xy[1])

    cnt_x = Counter(X).most_common()
    cnt_y = Counter(Y).most_common()
    return cnt_x[-1][0], cnt_y[-1][0]
    
coordinates = []
for _ in range(3):
    coordinates.append(list(map(int, input().split())))

x, y = get_square_coordinate(coordinates)
print (x, y)

crotia = ['c=', 'c-', 'dz=', 'd-', 'lj', 'nj', 's=', 'z=']
word = input()

for i in crotia:
    word = word.replace(i, '*')

print (len(word))

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main(void)
{
	string a, b;
	cin >> a >> b;
	if (a.size() == 3 and b.size() == 3)
	{
		reverse(a.begin(), a.end());
		reverse(b.begin(), b.end());
		if (a > b)
			cout << a;
		else
			cout << b;
	}
	return 0;
}

#include <iostream>
#include <cstdlib>
using namespace std;

int main(void)
{
	int H = 0;
	int M = 0;
	int T = 45;
	
	cin >> H >> M;
	
	if ((H>=0 and H<=23) and (M>=0 and M<=59))
	{
		
		if (M-T >= 0) // M이 45분보다 커서 자릿수 내림이 발생하지 않을 때 
		{
			cout << H << " " << M-T << endl;
		}
		
		if((M-T < 0) and (H-1>=0))
		{
			cout << H-1 << " " << M-T+60 << endl;
		}
		
		else if((M-T < 0) and (H-1<0))
		{
			cout << H-1+24 << " " << M-T+60 << endl;
		}
		
	}
	
	return 0;
}

import sys
input = sys.stdin.readline
N, M, K = list(map(int, input().split()))
team = 0

# my fault
# intern = 0
# while True:
#     if N//2 >= M:
#         N = N-1
#         intern = intern + 1
#         if K == intern:
#             break
    
#     elif N//2 < M:
#         M = M -1
#         intern = intern + 1
#         if K == intern:
#             break

# t1 = N // 2
# t2 = M 
# print(min(t1, t2))

while True:
    N = N - 2
    M = M - 1
    if N < 0 or M < 0 or (N+M) < K:
        break
    team = team + 1
print (team)

A, B = map(str, input().split())
if "6" in A or "6" in B:
    A = A.replace("6","5")
    B = B.replace("6","5")
_min = sum(map(int, [A, B]))

if "5" in A or "5" in B:
    A = A.replace("5","6")
    B = B.replace("5","6")
_max = sum(map(int, [A, B]))
print (_min, _max)

#include <iostream>

#define BIG 5
#define SMALL 3

using namespace std;

int Solution(int N)
{
	int quoteB = N / BIG; // 큰 설탕의 upper bound를 우선 결정
	
	while(true)
	{
		
		int Remainder = N - (BIG * quoteB); // 큰 설탕의 개수에 따라 나머지 결정 
		if (Remainder % SMALL == 0)	// 나머지가 작은 설탕으로 딱 떨어질 경우, 큰 설탕 개수 + 작은 설탕 개수 반환 
		{
			int quoteS = Remainder / SMALL;
			return quoteB+quoteS;
		}
		
		if (quoteB == 0)
			break;
			
		quoteB = quoteB -1;
	}
	
	return -1;
	
}

int main(void)
{
	int N = 0;
	
	cin >> N;
	
	if (N>=3 and N<=5000)
	{
		int result = Solution(N);
		cout << result;
	}
	
	return 0;
}

N, M = list(map(int, input().split()))
numbers = list(map(int, input().split()))
max = 0
for i in range(0, len(numbers)):
    for j in range(i+1, len(numbers)):
        for k in range(j+1, len(numbers)):
            temp = numbers[i] + numbers[j] + numbers[k]
            if temp > max and temp <=M:
                max = temp
print (max)

#include <iostream>
using namespace std;

bool checkLeapYear(int year)
{
	if ((year % 4 == 0 and year % 100 != 0) or (year % 4 ==0 and year % 400 == 0))
	{
		return true;
	}
	
	else
	{
		return false;
	}
}

int main(void)
{
	int result = -1; // 여부 확인 
	int year = 0; // 입력 연도 

	cin >> year;
	
	if (year>=1 and year<=4000)
	{
		result = checkLeapYear(year);
		cout << result << endl; 	
	}

	return 0;
}

import sys
input = sys.stdin.readline

fibo_nums = [0, 1]
for i in range(90):
    fibo_nums.append(sum([fibo_nums[-1], fibo_nums[-2]]))
    
n = int(input())
print (fibo_nums[n])